🧌 链表模板速览
📦 基础结构
1
2
3
4
| typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
|
1️⃣ 反转整个链表
思路： 三指针 prev / curr / next，逐个改指向。结束时 prev 就是新头。
1
2
3
4
5
6
7
8
9
10
11
| LinkList reverseList(LinkList head) {
if (head == NULL || head->next == NULL) return head;
LNode *prev = NULL, *curr = head;
while (curr != NULL) {
LNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
|
2️⃣ 删除指定值节点
思路： 用 dummy 哨兵节点统一处理头节点删除。遍历时判断 curr->next 的值，命中就跳过并 free。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| LinkList Del_x(LinkList head, int x) {
if (head == NULL) return NULL;
LNode dummy = {0, NULL};
dummy.next = head;
LNode *curr = &dummy;
while (curr != NULL) {
if (curr->next != NULL && curr->next->data == x) {
LNode *del = curr->next;
curr->next = curr->next->next;
free(del);
} else {
curr = curr->next;
}
}
return dummy.next;
}
|
3️⃣ 删除倒数第 k 个节点
思路： 快慢指针。fast 先走 k 步拉开间距，再走一步让 slow 停在被删节点的前驱，然后一起走到底。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| LinkList Del_k(LinkList head, int k) {
if (head == NULL || k <= 0) return head;
LNode dummy = {0, head};
LNode *fast = &dummy, *slow = &dummy;
for (int i = 0; i < k; i++) {
if (fast == NULL) return head;
fast = fast->next;
}
fast = fast->next;
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
LNode *del = slow->next;
if (del != NULL) {
slow->next = del->next;
free(del);
}
return dummy.next;
}
|
4️⃣ 反转前 n 个节点
思路： 和全反转一样，但只反转 n 个。反转结束后把原头的 next 接上剩余部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| LinkList reserve_n(LinkList head, int n) {
if (head == NULL || n <= 0) return head;
LNode *curr = head, *prev = NULL;
int count = 0;
while (curr != NULL && count < n) {
count++;
LNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = curr;
return prev;
}
|
5️⃣ 反转 m ~ n 区间（头插法）
思路： 找到第 m-1 个节点 pre，从 m+1 开始逐个头插到 pre 后面，循环 n-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
|
LinkList reverseBetween(LinkList head, int m, int n) {
if (head == NULL || m >= n) {
return head;
}
LNode dummy = {0, head};
LNode *pre = &dummy;
for (int i = 1; i < m; i++) {
if (pre->next == NULL) {
return head;
}
pre = pre->next;
}
LNode *start = pre->next;
if (start == NULL)
return head;
LNode *curr = start->next;
for (int i = 0; i < n - m; i++) {
start->next = curr->next;
curr->next = pre->next;
pre->next = curr;
curr = start->next;
}
return dummy.next;
}
|
6️⃣ 合并两个有序链表
思路： 双指针比较，小的先接到 tail 后，剩余直接拼。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| LinkList merge(LinkList head1, LinkList head2) {
LNode dummy = {0, NULL};
LNode *tail = &dummy;
LNode *p = head1, *q = head2;
while (p != NULL && q != NULL) {
if (p->data <= q->data) {
tail->next = p; p = p->next;
} else {
tail->next = q; q = q->next;
}
tail = tail->next;
}
tail->next = (p != NULL) ? p : q;
return dummy.next;
}
|
7️⃣ 判断环
思路： 快慢指针，fast 走两步、slow 走一步，相遇即有环。
1
2
3
4
5
6
7
8
9
| bool is_circle(LinkList head) {
LNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
|
8️⃣ 找中点
思路： 快慢指针，fast 到底时 slow 在中间。
⚠️ 左中点 vs 右中点（极度重要！）
以 1->2->3->4 为例：
| 写法 |
fast 初始化 |
slow 停在 |
适用场景 |
| 右中点 |
fast = head |
3（偏后） |
回文链表等 |
| 左中点 |
fast = head->next |
2（偏前） |
归并排序 / 链表分割 |
🚨 归并排序必须用左中点！ 右中点在 2 个节点时会导致死循环（切不开）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
LinkList find_mid(LinkList head) {
LNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
LinkList find_mid_left(LinkList head) {
LNode *slow = head, *fast = head->next;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
|
9️⃣ 判断回文链表
思路： ① 快慢指针找中点 → ② 反转后半段 → ③ 前后逐个比较。
💡 注意：此做法会修改原链表结构（反转了后半段）。工程中判断结束后通常需要再反转一次后半段复原链表。
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
| bool isPalindrome(LinkList head) {
if (head == NULL || head->next == NULL) return true;
LNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
if (fast != NULL) {
slow = slow->next;
}
LNode *prev = NULL, *curr = slow;
while (curr != NULL) {
LNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
LNode *p = head, *q = prev;
while (q != NULL) {
if (p->data != q->data) return false;
p = p->next; q = q->next;
}
return true;
}
|
🔟 K 个一组反转
思路： 找 k 个 → 断开 → 反转 → 接回 → 移动 pre，不足 k 个直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| LinkList reverseKGroup(LinkList head, int k) {
if (head == NULL || k <= 1) return head;
LNode dummy = {0, head};
LNode *pre = &dummy;
while (1) {
LNode *tail = pre;
for (int i = 0; i < k; i++) {
tail = tail->next;
if (tail == NULL) return dummy.next;
}
LNode *start = pre->next;
LNode *next = tail->next;
tail->next = NULL;
LNode *newHead = reverseList(start);
pre->next = newHead;
start->next = next;
pre = start;
}
}
|
1️⃣1️⃣ 链表归并排序
思路： 找中点 → 断开 → 递归排序左右 → merge 合并。经典分治。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| LinkList sortList(LinkList head) {
if (head == NULL || head->next == NULL) return head;
LNode *slow = head, *fast = head->next;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
LNode *mid = slow->next;
slow->next = NULL;
LNode *left = sortList(head);
LNode *right = sortList(mid);
return merge(left, right);
}
|
