链表：
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
链表类型：
1.单链表
单链表中的指针域只能指向节点的下一个节点。
2.双链表
每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表既可以向前查询也可以向后查询。
3.循环链表
链表首尾相连的叫循环链表。
循环链表可以用来解决约瑟夫环问题。
链表的存储方式：
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表的定义：
不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};链表的操作
1.删除节点
只要将C节点的next指针 指向E节点就可以了。
在C++中，D节点不是依然存留在内存里，只不过是没有在这个链表里而已。所以在C++里最好是再手动释放这个D节点，释放这块内存。
2.添加节点
可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。
数组和链表对比：
LeetCode203.移除链表元素
题目链接：203. 移除链表元素
思路：
移除操作将指针直接指向移除元素的下一个结点同时释放移除元素。
删除的如果是头结点：
- 直接使用原来的链表来进行删除操作。
- 设置一个虚拟头结点在进行删除操作。
如果不想单独删除头结点，则需要统一，那么该如何统一呢？
可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyhead = new ListNode(0);//设置一个虚拟头结点
dummyhead->next = head;//将dummyhead放在head前面
ListNode* cur = dummyhead;
while(cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else cur = cur->next;
}
return dummyhead->next;
}
};LeetCode707.设计链表
题目链接：707. 设计链表 - 力扣（LeetCode）
思路：
链表操作的两种方式：
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
LeetCode206.反转链表
题目链接：206. 反转链表 - 力扣（LeetCode）
思路：
双指针写法：
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
递归写法：
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。文章来源：https://www.toymoban.com/news/detail-505490.html
双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。文章来源地址https://www.toymoban.com/news/detail-505490.html
到了这里，关于代码随想录第三天|链表理论基础，LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
