链表理论基础
链表在逻辑结构上是线性表，在存储结构上是链式存储结构，即由一个个节点组成。
对应了STL中的vector。
链表的类型：
单链表、双链表、循环链表
链表的定义：
数据+指针
1
2
3
4
5
6
|
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
|
链表的主要操作：
1.删除节点：需要一个临时指针指向被删除的节点，然后令前面的next指针指向被删除节点的next。
2.插入节点：先上链（令新节点的next指向后者），再断链（令前者的next指向新节点）
删除链表元素
题目：203
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路：这里涉及到对于头节点的删除操作与其它节点不同，如果删除头节点，那么需要移动头指针；如果删除其它节点，不需要移动头指针。因此这里设置一个虚拟头节点，方便进行操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *v_head = new ListNode(0, nullptr);
v_head->next = head;
ListNode *cur = v_head;
while (cur->next != nullptr) {
ListNode *temp = cur->next;
if (temp->val == val) {
cur->next = temp->next;
delete temp;
} else {
cur = cur->next;
}
}
ListNode *temp = v_head;
v_head = v_head->next;
delete temp;
return v_head;
}
};
|
时间复杂度O(n)，遍历整个链表的时间；空间复杂度O(1)
收获：删除元素应该先保存链表下一个结点的信息
设计链表
题目：707
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
思路：这就是自己实现单链表的常用方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| class MyLinkedList {
public:
// 节点定义
struct Node {
int val; // 数据
Node *next; // 指针
Node() : val(0), next(nullptr) {}
Node(int val) : val(val), next(nullptr) {}
Node(int val, Node *next) : val(val), next(next) {}
};
int nums; // 链表长度，即元素个数
Node *head; // 头节点
public:
// constrcutor
MyLinkedList() {
// 创建头节点并初始化长度
head = new Node;
nums = 0;
}
// destructor
~MyLinkedList() {
if (nums > 0) {
Node *p = head->next;
while (p) {
Node *temp = p;
p = p->next;
delete temp;
}
}
delete head;
}
int get(int index) {
// 范围检查
if (index < 0 || index >= nums) return -1;
Node *temp = head->next; // 开始指向下标为0
// 下标每增加1向后移动1次
while (index--) temp = temp->next;
return temp->val;
}
void addAtHead(int val) {
// 创建新节点
Node *s = new Node(val, head->next);
head->next = s;
++nums;
}
void addAtTail(int val) {
// 找到最后一个节点
Node *p = head;
int count = nums;
while (count--) p = p->next;
// while (p->next != nullptr) p = p->next;
// 创建新节点
Node *s = new Node(val);
p->next = s;
++nums;
}
void addAtIndex(int index, int val) {
// 范围检查
if (index < 0 || index > nums) return;
// 找到第index-1个节点
Node *p = head;
while (index--) p = p->next;
Node *s = new Node(val, p->next);
p->next = s;
++nums;
}
void deleteAtIndex(int index) {
// 范围检查
if (index < 0 || index >= nums) return;
// 找到第index-1个节点
Node *p = head;
while (index--) p = p->next;
Node *temp = p->next;
p->next = temp->next;
--nums;
delete temp;
}
void print() {
if (nums == 0) {
cout << "链表为空" << endl;
return;
}
Node *p = head->next;
while (p) {
cout<< p->val << endl;
p = p->next;
}
}
};
|
收获：循环的时候注意循环体执行次数和循环判断条件的关系。
比如在上面的移动到需要的节点时，index–一共使得循环体执行index次，因此如果起点是head（相当于-1），那么最终指向第index-1个；如果起点是head->next(相当于0)，那么最终指向第index个节点。
翻转链表
题目：206
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路1：创建一个虚拟头节点，遍历单链表采用头插法插入节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| /**
* 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* reverseList(ListNode* head) {
// 创建一个虚拟头节点
ListNode *v_head = new ListNode;
// 遍历当前单链表
ListNode *cur = head;
while (cur != nullptr) {
ListNode *temp = cur->next; // 保存下一个节点信息
// 采用头插法插入cur节点
cur->next = v_head->next; // 令当前节点的next指针为空
v_head->next = cur;
// 更新当前节点
cur = temp;
}
// 删除虚拟头节点
ListNode *temp = v_head;
v_head = v_head->next;
delete temp;
return v_head;
}
};
|
时间复杂度O(n)，遍历单链表的时间；空间复杂度O(1)。
思路2：采用双指针，pre指针指向前一个节点，cur指向当前节点，每次处理两个节点的前后关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| /**
* 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* reverseList(ListNode* head) {
// 创建两个指针
ListNode *pre = nullptr, *cur = head;
// 遍历所有节点
// 每次处理两个节点的关系
while (cur != nullptr) {
// 保存当前节点的下一个节点信息
ListNode *temp = cur->next;
// 令当前节点指向前一个节点
cur->next = pre;
// 更新信息
pre = cur;
cur = temp;
}
// 当cur为空指针时
// pre刚好指向最后一个节点
// 将空指针想象为一个节点
return pre;
}
};
|
时间复杂度O(n)，遍历单链表；空间复杂度O(1)
思路3：重复的操作可以使用递归实现，即将思路2中不断对于两个结点进行翻转的操作封装成函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
ListNode *reverse(ListNode *pre, ListNode *cur) {
if (cur == nullptr) return pre;
ListNode *temp = cur->next;
cur->next = pre;
return reverse(cur, temp);
}
};
|
时间复杂度O(n)，处理每一个节点；空间复杂度O(n)，递归所使用的栈的空间
思路4：另一种形式的递归：每次都先翻转后面的链表，后面链表翻转完成之后再进行当前结点的翻转，注意这个递归返回的是最后一个节点值。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return head;
if (head->next == nullptr) return head; // 递归终止条件
ListNode *last = reverseList(head->next); // 先处理后面的反向
head->next->next = head;
head->next = nullptr;
return last; // 传递反向之后的头结点，也就是最后一个结点
}
};
|
思路5：栈：遍历一遍链表然后入栈，之后出栈即可。
时间复杂度O(n)；空间复杂度O(n)
两两交换链表中的结点
题目：24
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路：本题思路与上一题类似，但是在处理过程中，不仅需要关注当前交换位置的两个节点，而且需要关注当前两个节点交换位置之后与前面节点的关系。因此处理时应该保存前面一对的第二节节点信息，与当前这一对的两个节点信息。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| /**
* 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* swapPairs(ListNode* head) {
// 创建虚拟头节点
ListNode *v_head = new ListNode;
v_head->next = head;
ListNode *cur = v_head;
// 每次处理两个节点
// 但是需要包含三个节点
while (cur->next != nullptr && cur->next->next != nullptr) {
ListNode *first = cur->next;
ListNode *second = first->next;
ListNode *temp = second->next; // 保存下一对节点的第一个节点信息
// 交换节点
cur->next = second;
second->next = first; // 令后者指向前者
first->next = temp; // 令前者指向下一对
// 更新节点
cur = cur->next->next;
}
// 删除虚拟头节点
ListNode *temp = v_head;
v_head = v_head->next;
delete temp;
return v_head;
}
};
|
时间复杂度O(n)，空间复杂度O(1)
删除链表中的倒数第n个结点
题目：19
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
思路：找到倒数第n个节点的方法：从虚拟头节点开始，第一个指针先走n-1步指向第n-1个节点，接着第二个指针从头开始跟着第一个结点一起走到尾，假设最后一个节点为第len个，那么此时第一个指针和第二个指针一起走了len-n+1步，就会指向第len-n+1也就是倒数第n个结点。（倒数第1个节点是正数第len个，倒数第2个节点是正数第len-1个，以此类推，倒数第n个节点就是正数第len-n+1个）
但是这题是删除倒数第n个，所以需要实际上需要找到倒数第n-1个节点。第一个指针需要先走n步，指向第n个节点，然后两个指针一起走，此时第二个指针移动了len-n指向第len-n个节点，也就是倒数第n+1个节点。
PS：虚拟头结点的好处就是对于第一个结点的操作与其他结点一样，没有虚拟头节点对于头结点的操作需要单独处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *v_head = new ListNode;
v_head->next = head;
ListNode *first = v_head;
while (n--) first = first->next;
ListNode *second = v_head;
while (first->next) {
first = first->next;
second = second->next;
}
ListNode *target = second->next;
second->next = target->next;
delete target;
target = v_head;
v_head = v_head->next;
delete target;
return v_head;
}
};
|
时间复杂度O(n)，遍历链表的时间；空间复杂度O(1)
链表相交
题目160
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
思路1：链表A+链表B，判断是否存在循环。判断循环链表的方法：使用双指针，快指针每次向后移动两个位置，慢指针每次移动一个位置。如果是循环链表，那么两个指针会在某个节点相遇即节点相同。进入循环条件是快指针后面存在两个节点。如果单链表存在环，则循环不会终止，需要在两个节点相遇时break。如果不存在环，那么一定能够跳出while。
判断存在环之后，还需要找到环的起点：1.使用快慢指针寻找相遇点；2.当第一次相遇时，令其中一个指针指向头结点，两个指针同速前进，再次相遇点就是环的起点。
原理是假设有三个点：头结点、环的起点、相遇点，相遇点一定在环的起点之后（没到环的起点怎么相遇）。
假设相遇点时slow走了k，那么fast一定走了2k，多走的这一部分是在环中转圈，所以多走的这一部分k一定是环的长度的n倍。
假设相遇点距离环的起点的距离为m，那么环的起点点距离头结点的距离为k-m；即从头结点走k-m到达环的起点。
假如从相遇点开始走，再走k一定是重新到达相遇点。那么现在两个指针都走k-m会到环的起点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) return nullptr;
ListNode *end = headA;
while (end->next) end = end->next;
end->next = headB;
ListNode *slow, *fast;
slow = fast = headA;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
if (slow == fast) {
fast = headA;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
end->next = nullptr;
return slow;
}
}
end->next = nullptr;
return nullptr;
}
};
|
时间复杂度O(max(N + M))，以慢指针为例，最差在最后的位置相遇，然后再移动小于N+M的长度；空间复杂度O(1)
思路2：将链表A+链表B 链表B+链表A，使用两个指针遍历这两个链表，如果存在相交结点，那么一定相遇在空结点之前。如果不存在相交节点，那么最终相遇的位置是末尾的空结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
while (pA != pB) {
if (pA == nullptr) pA = headB;
else pA = pA->next;
if (pB == nullptr) pB = headA;
else pB = pB->next;
}
return pA;
}
};
|
时间复杂度O(max(N + M))，最差会走两个链表的长度之和；空间复杂度O(1).
作者的思路：求两个链表长度，总之与思路1一样
环形链表
题目：142
主要思路：1.使用快慢指针寻找相遇点；2.当第一次相遇时，令其中一个指针指向头结点，两个指针同速前进，再次相遇点就是环的起点。
有三个点：头结点、环的起点、相遇点，相遇点一定在环的起点之后（没到环的起点怎么相遇）。
假设相遇点时slow走了k，那么fast一定走了2k，多走的这一部分是在环中转圈，所以多走的这一部分k一定是环的长度的n倍。
假设相遇点距离环的起点的距离为m，那么环的起点点距离头结点的距离为k-m；即从头结点走k-m到达环的起点。
假如从相遇点开始走，再走k一定是重新到达相遇点。那么现在两个指针都走k-m是到环的起点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == nullptr) return nullptr;
ListNode *slow, *fast;
slow = fast = head;
while (fast->next && fast ->next->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
fast = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return nullptr;
}
};
|
时间复杂度O(n)，快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于 2n；空间复杂度O(1)
总结
链表的基础知识：
- 链表的种类主要为：单链表，双链表，循环链表
- 链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
- 链表是如何进行增删改查的。
- 数组和链表在不同场景下的性能分析。
虚拟头节点：链表的一大问题就是操作当前节点必须要找前一个节点才能操作。这就造成了，头结点的尴尬，因为头结点没有前一个节点了。每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。
链表的基础操作：
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点的数值
反转链表：迭代法：每次操作相邻的两个节点，交换两个节点的指向。这里需要注意的是每次处理当前指针时需要了解上一个指针的信息以及保存下一个节点的信息。
采用头插法：类似于栈的操作。
删除倒数第N个节点：主要思想是两个指针的移动找到倒数的节点，第一个指针先移动n-1，然后两个指针一起移动直到第一个指针指向最后一个节点，这样第二个指针就移动了len-n+1，也就是倒数第N个节点。
另外，删除链表的元素可以删除该结点的后一个元素，即先让当前节点的值为后一个节点的值，然后删除后一个节点。
链表相交和环形链表：主要是利用双指针进行操作，包括寻找环、以及判断环的入口位置。