前言

链表题的代码通常不超过二十行，但错误率很高。原因不是算法难，而是链表没有下标、不能随机访问，每一步操作都要自己维护"前驱、当前、后继"三个关系；一旦改链顺序错了，轻则断链，重则访问已释放的结点。

这五道题覆盖了链表操作最核心的几类技巧：三指针反转、哑结点尾插、长度差对齐、前驱改链去重、快慢指针找中点。把它们写熟，大部分链表题都能拆成这几个动作的组合。

本文每道题给出思路、完整函数和复杂度，最后用一段main串起来。所有代码以 C++17 为基准，结点由new分配、由统一的destroy释放，避免示例本身泄漏。

// 适用于 C++17
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int v) : val(v), next(nullptr) {}
};

一、反转链表

题目：给定单链表头结点，返回反转后的头结点。

思路：维护三个指针prev、cur、next。每一步先用next保存cur的后继（否则改完cur->next就找不到后面了），再把cur->next指向prev，然后三者一起前移。循环结束时cur为空，prev就是新头。

// 适用于 C++17
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* next = cur->next; // 先保存后继
cur->next = prev; // 再改指向
prev = cur; // 前移
cur = next;
}
return prev;
}

顺序不能换：如果先写cur->next = prev再去取cur->next，拿到的已经是prev，链表从中间断开。时间 O(n)，空间 O(1)。

二、合并两个有序链表

题目：把两个升序链表合并成一个升序链表，要求原地拼接，不新建结点。

思路：哑结点 + 尾指针。每次比较两个链表当前结点的值，把较小的那个接到尾部，然后该链表前移。一个链表走完后，把另一个链表剩余部分整体接上。

// 适用于 C++17
ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* tail = &dummy;

while (a != nullptr && b != nullptr) {
if (a->val <= b->val) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = (a != nullptr) ? a : b; // 剩余部分整体挂上
return dummy.next;
}

返回dummy.next而不是dummy：dummy是栈对象，函数结束即销毁。用<=而不是<可以让相等元素保持"先 a 后 b"，使合并过程稳定，但这只是习惯，题目通常不要求。

时间 O(m + n)，空间 O(1)。

三、相交链表

题目：判断两个单链表是否相交，若相交返回第一个公共结点。

思路：先各求一次长度，让较长的链表先走长度差的步数，使两个指针到末尾的距离相等；然后同步前进，第一次指针相等的位置就是交点。注意比较的是结点地址，不是val。

// 适用于 C++17
int listLength(const ListNode* head) {
int n = 0;
for (const ListNode* p = head; p != nullptr; p = p->next) ++n;
return n;
}

ListNode* getIntersectionNode(ListNode* a, ListNode* b) {
int la = listLength(a);
int lb = listLength(b);
while (la > lb) { a = a->next; --la; }
while (lb > la) { b = b->next; --lb; }
while (a != b) { a = a->next; b = b->next; }
return a; // 不相交时同时为空，返回 nullptr
}

while (a != b)在两者都为空时也会退出，返回nullptr，正好表示不相交，不需要额外分支。

时间 O(m + n)，空间 O(1)。另一种写法是走完自己的链表后跳到对方头部，两趟后必然在交点或空处相遇，代码更短，但步数关系不如长度差直观。

四、删除排序链表中的重复元素

题目：给定升序链表，删除重复结点，使每个值只出现一次。

思路：因为有序，重复元素必然相邻。用一个指针cur，比较cur与cur->next：相等就删掉cur->next，cur不动（可能还有第三个重复）；不等才前移。

// 适用于 C++17
ListNode* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->val == cur->next->val) {
ListNode* dup = cur->next;
cur->next = dup->next;
delete dup; // 释放被跳过的结点
} else {
cur = cur->next; // 只有不相等时才前移
}
}
return head;
}

这里的关键是"删完不前进"：1 -> 1 -> 1时，第一轮删掉第二个 1，cur仍指向第一个 1，下一轮再删第三个。如果删完就cur = cur->next，会漏掉连续的第三个重复。

如果题目要求"重复的一个都不留"（LeetCode 82），则需要哑结点加双层循环，逻辑不同，不能直接套用。

五、链表的中间结点

题目：返回链表的中间结点；偶数个结点时返回第二个中间结点。

思路：快慢指针。慢指针每次走一步，快指针每次走两步。快指针到末尾时，慢指针正好在中间。

// 适用于 C++17
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

循环条件必须写成fast != nullptr && fast->next != nullptr，顺序不能反：fast为空时再取fast->next就是解引用空指针。对于1 -> 2 -> 3 -> 4，快指针走两步到 3，再走两步到空，慢指针停在 3，即第二个中间结点；若要第一个中间结点，把循环条件改成fast->next != nullptr && fast->next->next != nullptr。

时间 O(n)，空间 O(1)。

六、共性总结

把五道题串起来跑一遍，顺便验证各函数对空链表的处理：

// 适用于 C++17
#include <iostream>

ListNode* build(std::initializer_list<int> vals) {
ListNode dummy(0);
ListNode* tail = &dummy;
for (int v : vals) {
tail->next = new ListNode(v);
tail = tail->next;
}
return dummy.next;
}

void destroy(ListNode* head) {
while (head != nullptr) {
ListNode* next = head->next;
delete head;
head = next;
}
}

int main() {
ListNode* a = build({1, 3, 5});
ListNode* b = build({2, 4, 6});
ListNode* merged = mergeTwoLists(a, b); // 1 2 3 4 5 6
merged = reverseList(merged); // 6 5 4 3 2 1
merged = deleteDuplicates(merged); // 无重复，原样
ListNode* mid = middleNode(merged); // 指向 3

std::cout << mid->val << '\n';
destroy(merged);
return 0;
}

注意mergeTwoLists之后，原来的a、b头指针已经不能单独用来释放了——结点已经被串进新链表，所有权转移给了merged。这也是链表题里常见的所有权陷阱：谁最后持有整条链，谁负责释放。

常见坑点

1. 反转时先改指向再保存后继

// ❌ 后继丢失，链表从中间断开
cur->next = prev;
ListNode* next = cur->next;
// ✅ 先保存，再改
ListNode* next = cur->next;
cur->next = prev;

2. 合并时返回哑结点本身

// ❌ 返回栈对象指针，函数结束即悬垂
return &dummy;
// ✅ 返回哑结点的后继
return dummy.next;

3. 判断相交时比较值

// ❌ 值相等不代表同一个结点
while (a->val != b->val) { ... }
// ✅ 比较结点地址
while (a != b) { a = a->next; b = b->next; }

4. 去重时删完立即前移

// ❌ 连续三个相同值时漏删
cur->next = dup->next;
cur = cur->next;
// ✅ 删完停在原地，下一轮继续比较
cur->next = dup->next;

5. 快指针直接取fast->next->next

// ❌ fast 或 fast->next 为空时解引用
while (fast->next->next) { ... }
// ✅ 两级判空
while (fast != nullptr && fast->next != nullptr) { ... }

6. 释放了结点却仍在使用

// ❌ dup 已释放，next 是悬垂读取
delete dup;
cur->next = dup->next;
// ✅ 先改链，再释放
cur->next = dup->next;
delete dup;

7. 空链表没有处理

// ❌ head 为空时解引用
int n = head->val;
// ✅ 先判空，或让循环条件自然处理
while (head != nullptr) { ... }

总结

链表题看起来零散，实际只有几个动作：保存后继、改指向、移动指针、处理边界。每写一步都问自己"这个指针现在指向哪、它还有效吗"，比记住某道题的标准答案更有用。