链表理论基础
1、基本类型：单链表、双链表、循环链表
2、存储方式：和数组不一样，链表是随机存储在内存中，不是连续分配在内存中。
3、链表的定义：
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};
定义了一个数据域，还有一个指针域，并且定义了一个构造函数。
4、链表的操作：
删除节点：
在图中，若需要删除D这个节点，只需要让C的指针域指向E就行了，然后手动删除D节点就完成了删除节点的操作。
增加节点：
在这个图中，添加一个节点F，只需要将C的指针域指向F，F的指针域指向D，完成添加节点的操作。
5、性能分析
相较于数组来说，链表插入和删除的时间复杂度为O(1),但是查找复杂度是O(n),下面给出一个图做比较。
移除链表的元素
基本思路就是将第二个和第四个节点从链表中删除：
这样的话会遇到一种问题，如果我们的需要删除的元素是头节点怎么办，我们可以对头节点的情况再做一个特殊情况处理，但是我们可以通过一种构造一种虚拟头节点的办法来统一操作。虚拟头节点的思想很简单，就是在头节点之前再给出一个节点，这样以来处理所有的节点都是同种操作。
/**
* 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;//虚拟头节点的指针指向头节点
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;
}
}
head = dummyHead->next;
delete dummyHead;
return head;
}
};需要注意的点是，在删除节点的时候，需要设置一个临时节点等于那个节点，删除那个节点。
同时，在已经有dummyhead的情况下，为什么需要再设置一个cur来进行后续的操作。这是因为虚拟头节点是不可以变的，若后面的cur都以dummyhead操作，dummyhead最后就变成了最后一个节点，虚拟头节点的位置应该保持不变，在最后返回头节点指向的指针就可以了。
设计链表
这道题相当于设计链表的五个接口，分别是：
获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点
class MyLinkedList {
public:
//定义一个链表节点的结构体
struct LinkedNode{
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
//定义链表
MyLinkedList() {
dummyHead = new LinkedNode(0);
size = 0;
}
// 获取第index个数的值
int get(int index) {
if(index > size - 1 || index < 0)//如果想要获取的值超出了链表长度或者非法，就返回-1
{
return -1;
}
LinkedNode* cur = dummyHead->next;
while(index--)
{
cur = cur->next;
}
return cur->val;
}
//在链表头插入元素
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);//要插入的元素
newNode->next = dummyHead->next;
dummyHead->next = newNode;
size++;
}
//在链表最后添加元素
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = dummyHead;
while(cur->next != NULL)
{
cur = cur->next;
}
cur->next = newNode;
size++;
}
//在链表第index个节点前面插入一个节点
void addAtIndex(int index, int val) {
if(index > size) return;
if(index < 0) index = 0;
LinkedNode* newNode = new LinkedNode(val);//创建一个新节点
LinkedNode* cur = dummyHead;
while(index--)
{
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
size++;
}
//删除链表的第index个节点
void deleteAtIndex(int index) {
if(index > size - 1 || index < 0)
{
return ;
}
LinkedNode* cur = dummyHead;
while(index--)
{
cur = cur->next;
}
LinkedNode *tmp = cur->next;
cur->next = tmp->next;
delete tmp;
size--;
}
private:
LinkedNode* dummyHead;
int size;
};这道题包含了链表操作的五大功能，值的注意的是错误条件的判断。
翻转链表
基本思路比较简单，只要让每一个链表节点的指向都相反，就能实现将整个链表反转的操作。 
这里的话我们使用双指针法， 使用两个指针，不断更新前后指针的位置达到反转链表的效果。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp;
ListNode* pre = head;
ListNode* cur = NULL;
while(pre)
{
temp = pre->next;
pre->next = cur;
cur = pre;
pre = temp;
}
return cur;
}
};重点在于我们需要定义一个指针temp一直指向pre的next，这样pre的next反转指向cur的时候，pre下一次还可以通过temp的位置来更新自己的下一次位置。文章来源：https://www.toymoban.com/news/detail-450103.html
这道题还可以使用递归的方法来做，代码如下：文章来源地址https://www.toymoban.com/news/detail-450103.html
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};到了这里，关于代码随想录day3｜链表理论基础、移除链表元素、设计链表、翻转链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
