前言
链表是一个不常使用在日常软件开发中的数据结构，但是，却经常会被用于出算法题，这是因为，链表的两个元素之间是通过next指针相连，如果没有维护好这个指针信息，就会导致无法访问到某一元素。
我们一般使用单向链表，其中每个元素的结构包括一个data变量和一个next指针，前者用于存储数据，后者用于记录下一个元素的地址，C语言的表示为：
1
2
3
4
| typedef struct LinkedListNode {
int data;
struct LinkedListNode* next;
} LLN;
|
简单的例子：反转链表
这道题可以通过LeetCode 206访问，这道题的一个AC解是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL || head->next == NULL) {
return head;
}
struct ListNode* prev = NULL;
struct ListNode* curr = head;
struct ListNode* neno = head->next;
while(curr != NULL) {
curr->next = prev;
prev = curr;
curr = neno;
neno = (neno == NULL) ? NULL : neno->next;
}
return prev;
}
|
在循环内，neno的赋值选择注释掉的一行还是未注释的一行都可以。只涉及$O(1)$空间复杂度的链表反转，重要之处在于**如何维护next**节点的信息。因为，当反转链表时，由于next指向的问题，如果不维护下一个节点的信息，那么下一次迭代就没有办法访问了。
所以这道题的逻辑是这样的：
- 下一个节点的维护：记录当前节点的下一个节点。
- 主要逻辑：反转当前节点的下一节点指向。
- 为下一次迭代做准备：即
prev和curr节点的赋值。
只要是涉及链表的算法，最重要的就是如何维护下一个节点的信息。
简单的例子：合并两个排好序的链表
这道题可以通过LeetCode 21访问，这道题的一个AC解是：
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
|
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = 0;
head->next = NULL;
struct ListNode* curr = head;
struct ListNode* p1 = list1;
struct ListNode* p2 = list2;
while(p1 != NULL || p2 != NULL) {
if(p2 == NULL) {
curr->next = p1;
p1 = p1->next;
} else if(p1 == NULL) {
curr->next = p2;
p2 = p2->next;
} else {
if(p1->val >= p2->val) {
curr->next = p2;
p2 = p2->next;
} else {
curr->next = p1;
p1 = p1->next;
}
}
curr = curr->next;
}
return head->next;
}
|
值得注意的是，我不推荐任何人使用C去进行LeetCode的作答，比如malloc后的赋值操作，对于算法没有任何影响，但是删除这两句，便无法AC。
这道题就很好体现了我们之前说的三个步骤：
- 下一个节点的维护：划分不同条件，根据空指针、值大小判断当前节点接续什么节点。
- 主要逻辑：接续的过程。
- 为下一次迭代做准备：将
curr节点变作它的下一个节点。
中等的例子：快慢指针
这道题可以通过LeetCode 141访问，一个AC解是：
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
|
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == nullptr) {
return false;
}
ListNode* slowp = head, *fastp = head->next;
while(slowp != fastp) {
if(fastp == nullptr || fastp->next == nullptr) {
return false;
}
slowp = slowp->next;
fastp = fastp->next->next;
}
return true;
}
};
|
这道题的关键在于，一个链表如果有环，那么迭代将永远无法遇到空指针，并且利用不同速度迭代，将会相遇。那么，我们可以让一个指针走得快一些，一个指针慢一些，如果遇到了空指针，就是无环，如果相遇了就是有环。
这道题同样是三个步骤：
- 下一个节点的维护：确定快慢指针的落点。
- 主要逻辑：是否遇到空指针？是否快慢指针相遇？
- 为下一次迭代做准备。
中等的例子：链表的重排
这道题可以通过LeetCode 143访问，一个AC解是：
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
|
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* curr = head;
vector<ListNode*> v;
while(curr != nullptr) {
v.push_back(curr);
curr = curr->next;
}
curr = head;
for(int i = 0; i < v.size() / 2; ++i) {
if(i != 0) {
curr->next = v[i];
curr = curr->next;
}
curr->next = v[v.size() - i - 1];
curr = curr->next;
}
if(v.size() % 2 == 1) {
curr->next = v[v.size() / 2];
curr = curr->next;
}
curr->next = nullptr;
}
};
|
这道题的重要之处在于后续节点的处理，尤其是最后一行——最后一个节点的next节点要清空。其实这道题本身不难，只是最后一行的curr->next=nullptr;如果没有想到，会花掉大量的调试时间。
中等的例子：深度拷贝链表
这道题可以通过LeetCode 138访问，一个AC解是：
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
|
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> um;
Node* curr = head;
while(curr != nullptr) {
Node* copy = (Node*)malloc(sizeof(Node));
copy->val = curr->val;
copy->next = nullptr;
copy->random = nullptr;
um.insert({curr, copy});
curr = curr->next;
}
curr = head;
while(curr != nullptr) {
um[curr]->next = um[curr->next];
um[curr]->random = um[curr->random];
curr = curr->next;
}
return um[head];
}
};
|
这道题的重要之处在于，通过一种连接索引关系，恢复另一种索引关系。先根据next深度拷贝每个节点，然后根据next节点的索引关系恢复random节点。
