前言链表题的代码通常不超过二十行但错误率很高。原因不是算法难而是链表没有下标、不能随机访问每一步操作都要自己维护前驱、当前、后继三个关系一旦改链顺序错了轻则断链重则访问已释放的结点。这五道题覆盖了链表操作最核心的几类技巧三指针反转、哑结点尾插、长度差对齐、前驱改链去重、快慢指针找中点。把它们写熟大部分链表题都能拆成这几个动作的组合。本文每道题给出思路、完整函数和复杂度最后用一段main串起来。所有代码以 C17 为基准结点由new分配、由统一的destroy释放避免示例本身泄漏。// 适用于 C17struct 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就是新头。// 适用于 C17ListNode* 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)。二、合并两个有序链表题目把两个升序链表合并成一个升序链表要求原地拼接不新建结点。思路哑结点 尾指针。每次比较两个链表当前结点的值把较小的那个接到尾部然后该链表前移。一个链表走完后把另一个链表剩余部分整体接上。// 适用于 C17ListNode* 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而不是dummydummy是栈对象函数结束即销毁。用而不是可以让相等元素保持先 a 后 b使合并过程稳定但这只是习惯题目通常不要求。时间 O(m n)空间 O(1)。三、相交链表题目判断两个单链表是否相交若相交返回第一个公共结点。思路先各求一次长度让较长的链表先走长度差的步数使两个指针到末尾的距离相等然后同步前进第一次指针相等的位置就是交点。注意比较的是结点地址不是val。// 适用于 C17int 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-nextcur不动可能还有第三个重复不等才前移。// 适用于 C17ListNode* 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时第一轮删掉第二个 1cur仍指向第一个 1下一轮再删第三个。如果删完就cur cur-next会漏掉连续的第三个重复。如果题目要求重复的一个都不留LeetCode 82则需要哑结点加双层循环逻辑不同不能直接套用。五、链表的中间结点题目返回链表的中间结点偶数个结点时返回第二个中间结点。思路快慢指针。慢指针每次走一步快指针每次走两步。快指针到末尾时慢指针正好在中间。// 适用于 C17ListNode* 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)。六、共性总结题目核心技巧关键边界时间反转链表三指针先存后继空链表、单结点O(n)合并有序链表哑结点 尾插一方先走完O(mn)相交链表长度差对齐不相交返回空O(mn)删除重复前驱改链删后不前移连续三个以上重复O(n)中间结点快慢指针偶数取第二个O(n)把五道题串起来跑一遍顺便验证各函数对空链表的处理// 适用于 C17#include iostreamListNode* build(std::initializer_listint 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 6merged reverseList(merged); // 6 5 4 3 2 1merged deleteDuplicates(merged); // 无重复原样ListNode* mid middleNode(merged); // 指向 3std::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) { ... }总结技巧适用题型记忆点三指针反转反转、部分反转先存后继再改指向哑结点删头、合并、插入返回dummy.next长度差对齐相交、倒数第 N 个先让长的走差值前驱改链删除、去重删完不前移快慢指针中点、环、倒数快指针两步注意判空链表题看起来零散实际只有几个动作保存后继、改指向、移动指针、处理边界。每写一步都问自己这个指针现在指向哪、它还有效吗比记住某道题的标准答案更有用。