链表基础
c/c++中链表是通过指针串联在一起的线型结构，指针串联起了一个个节点
每个节点都有数据域和指针域（单链表有一个指针域，双链表有两个指针域，当然也可以有多个指针...）
最后一个节点的指针指向空，null
入口出的节点我们一般叫做头节点，head
链表在内存中不是连续的，取决于操作系统的内存管理
单链表：上图
双链表：
- 因为有两个指针，多以指向就有更多的可选择性
- 一般一个指针指向上一个节点，另一个指针指向下一个节点，第一个节点的prev和最后一个节点的next指向null
- 支持向前查询也支持向后查询
循环链表
- 顾名思义就是链表的头尾节点通过指针指向的方式首尾相接
- 约瑟夫环问题用循环链表做很快啊
自己定义链表节点
定义单链表：
struct ListNode {
//数据域
int val;
//指针域
ListNode* next;
//自定义节点构造函数
ListNode(int x) :val(x), next(NULL) {}
};
有构造函数就会比较方便一点，可以进行如下初始化：
ListNode* head = new ListNode(555); cout << head->val << " "<< head <<" "<< head->next;
否则初始化要这样：
ListNode* head = new ListNode(); head->val = 5;
删除节点
要删第i个节点，把第i-1个节点的next指向第i+1个节点，然后手动释放掉第i个节点的内存（c++中最好是手动释放，python中交给内存机制就好了）
添加节点
要添加节点，也是修改插入位置的前后指针的指向
插入和删除节点的操作复杂度都是$O(1)$但是查询是$O(n)$
数组和链表的对比
| 插入/删除的时间复杂度 | 查询的时间复杂度 | 使用场景 | |
| 数组 | $O(n)$ | $O(1)$ |
数据量固定 频繁查询 较少增删 |
| 链表 | $O(1)$ | $O(n)$ |
数据量不固定 较少查询 频繁增删 |
虚拟的头节点
写代码时候发现，移除头节点和移除中间的节点操作不太一样的，所以为了统一代码，只需要设置一个虚拟的头节点，指向原先的头节点
最后返回虚拟头节点的下一个节点就好。
return dummyNode->next;
移除链表元素
题目：删除链表中等于给定值 val 的所有节点。
203. 移除链表元素 - 力扣（LeetCode） (leetcode-cn.com)
不使用虚拟头节点在原先代码上改：
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next != NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else {
cur = cur->next;
}
}
return head;
}
使用虚拟的头节点：
ListNode* removeElements2(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向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;
}
设计链表
有一些题目考察链表的设计，写出链表的基本功能，考察代码的掌控程度。
707. 设计链表 - 力扣（LeetCode） (leetcode-cn.com)
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
//设计链表，实现链表的基本接口
class MyListSolution {
public:
struct myListNode {
int val;
myListNode* next;
myListNode(int val) : val(val), next(nullptr) {}
};
//初始化链表，即构造函数
MyListSolution() {
_dummpyHead = new myListNode(0);
_size = 0;
}
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if (index < 0 || index >= _size) return -1;
myListNode* cur = _dummpyHead;
while (index--) {
cur = cur->next;
}
//cout << cur->val << endl;
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
if (_dummpyHead->next != NULL) {
myListNode* tmp = new myListNode(val);
tmp->next = _dummpyHead->next;
_dummpyHead->next = tmp;
_size += 1;
}
myListNode* tmp = new myListNode(val);
_dummpyHead->next = tmp;
_size += 1;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
myListNode* tmp = new myListNode(val);
myListNode* cur = _dummpyHead;
while (cur->next != NULL) {
cur = cur->next;
}
cur->next = tmp;
_size += 1;
}
// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
void addAtIndex(int index, int val) {
if (index > _size) {
return;
}
else if (index <= 0) {
addAtHead(val);
}
else if (index == _size) {
addAtTail(val);
}
else {
myListNode* tmp = new myListNode(val);
myListNode* cur = _dummpyHead;
while (index--) {
cur = cur->next;
}
//cur->next是目标位置
tmp->next = cur->next;
cur->next = tmp;
_size+=1;
}
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
void delAtIndex(int index) {
if (index >= _size || index < 0) {
return;
}
myListNode* cur = _dummpyHead;
while (index--) {
cur = cur->next;
}
//cur->next是目标位置
myListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size -= 1;
}
// 打印链表
void printMyList() {
myListNode* cur = _dummpyHead;
while (cur->next != NULL) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
myListNode* _dummpyHead;
};
int main() {
//ListNode* head = new ListNode(555);
//cout << head->val << " "<< head <<" "<< head->next;
MyListSolution *test = new MyListSolution();
test->addAtHead(1);
test->addAtTail(3);
test->addAtIndex(1, 2);
test->printMyList();
test->get(1);
test->delAtIndex(1);
test->get(1);
test->printMyList();
return 0;
}
如果设置了虚拟头节点，那么当执行下面代码后
myListNode* cur = _dummpyHead;
while (index--) {
cur = cur->next;
}
当index=0后，不会执行while部分代码，跳出循环。
反转链表
这道题做过，demo....数据结构入门 - PiaYie - 博客园 (cnblogs.com)
反转一个单链表，例如经典题目：206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
双指针
为什么叫双指针解法？
首先肯定有一个cur指针，从前移到后面，需要更改的是cur的指向，指向的还是前一个节点，咋一看，欸还没有东西表示前一个节点，so，要用一个指针prev来表示cur的前一个节点。
//反转链表
class reverseListSolution {
public:
ListNode* reverseList(ListNode* head) {
//利用双指针迭代
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* temp = new ListNode();
while (cur) {
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
递归
函数调用是递归的根据栈实现。
使用递归必须要满足的两个条件就是：
- 要有递归公式。
- 要有终止条件。
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
这里终止条件是当head或者head->next指向NULL的时候。
递归公式是返回新链表的头节点（==啊啊啊啊草啊啊啊啊不理解）
//递归方法1
ListNode* reverseList2(ListNode* head) {
//递推公式reverseList2的含义是：把拿到的链表进行反转，然后返回新的头结点newHead
if (!head || !head->next) {
return head; //注意这个head指向最后一个节点最后一路返回
}
//使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 newHead .
ListNode* newHead = reverseList2(head->next);
//此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
head->next->next = head;
//同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
head->next = nullptr;
//当递归函数全部出栈后，链表反转完成。
return newHead;
}
最后返回是 return <= newhead1 <= newhead2 <= newhead3 <= newhead4 <=newhead5 = head = [5]
反转链表代码
//反转链表
class reverseListSolution {
public:
//双指针迭代法
ListNode* reverseList(ListNode* head) {
//利用双指针迭代
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* temp = new ListNode();
while (cur) {
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
//递归方法1
ListNode* reverseList2(ListNode* head) {
//递推公式reverseList2的含义是：把拿到的链表进行反转，然后返回新的头结点newHead
if (!head || !head->next) {
return head; //newHead在这呢我吐了
}
ListNode* newHead = reverseList2(head->next);
//使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 retret .
//此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
//同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
//当递归函数全部出栈后，链表反转完成。
head->next->next = head;
head->next = nullptr;
return newHead;
}
//递归方法2
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* reverseList3(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};