1. 链表专题的整体思路与前置知识1.1 为什么链表题值得单独拿出来练链表在 LeetCode Hot 100 里看起来题量不大但含金量非常高。我自己的刷题顺序是先把数组、哈希表、双指针这些“线性思维”的题过一遍再集中刷链表。为什么因为链表题几乎是 C 指针操作的最佳训练场它不像数组那样可以用下标直接访问每一步操作都要求你清楚地知道当前指针在哪、下一个节点是谁、修改完之后还有没有路径走回去。这五道题——反转链表、合并两个有序链表、删除链表的倒数第 N 个结点、环形链表、环形链表 II基本涵盖了链表题最核心的几种范式指针反转、哑节点、快慢双指针、数学推导。把这五道题吃透后面再做链表相关的进阶题比如 K 个一组翻转链表、排序链表思路会顺畅很多。这篇笔记适合已经把链表基本结构搞明白、但做题时总是卡在指针细节上的同学。也适合准备面试、希望把常见链表题型形成肌肉记忆的人。我尽量把每一步的“为什么”讲清楚而不是只贴一份能通过的代码。1.2 刷链表题之前先把两个基本功练熟第一个基本功是写一个能随时打印链表的辅助函数。链表题最痛苦的时候不是不会做而是代码写完跑起来直接段错误或者死循环卡死你根本不知道指针错在哪一步。我一般会在本地环境里写一个printListvoid printList(ListNode* head) { ListNode* cur head; while (cur) { cout cur-val - ; cur cur-next; } cout nullptr endl; }这个函数看起来不起眼调试时比什么工具都好用。每操作完一个关键步骤就打印一次指针指到哪、有没有断链一目了然。第二个基本功是画图。我说的是真画拿纸笔把每个节点画成方框把指针画成带箭头的线每一步操作之后重新画一遍。尤其是反转链表和环形链表这种“指针绕来绕去”的题脑内模拟很容易出错纸面上画几遍规律就清晰了。很多同学觉得画图浪费时间但我实测下来画一张图能省下半小时的调试时间。2. 反转链表LeetCode 206最经典的链表入门题2.1 迭代三指针法先保存再反转最后移动题目很直白给你单链表的头节点head反转链表返回反转后的链表头。示例是1-2-3-4-5-NULL反转后变成5-4-3-2-1-NULL。我第一次写这道题的时候代码是这样的ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; // 先保存下一个节点 cur-next pre; // 反转指针方向 pre cur; // pre 前进 cur next; // cur 前进 } return pre; }核心操作就一句cur-next pre。但就这么一句话背后藏着三个关键细节。第一个细节是必须先保存next。当我把cur-next指向pre之后原来cur后面的节点就再也找不到了链表在这里断掉了。所以必须先用一个临时变量把下一个节点记下来等反转完成后把cur移过去。第二个细节是pre的初始值必须是nullptr。反转之后原来的头节点变成尾节点它的next应该指向空。如果初始pre设成head自己结果链表会成环。第三个细节是返回值必须是pre而不是cur。循环结束时cur已经变成nullptr真正的头节点是pre也就是原链表的尾节点。这个版本的时间复杂度 O(n)空间复杂度 O(1)也是面试里最标准的写法。2.2 递归写法一旦理解了代码比迭代更简短递归版本大概是这样的ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }递归写法的关键在于想清楚reverseList(head-next)返回的是什么它返回的是以head-next为起点、反转之后的新链表头。假设2-3-4-5已经反转成了5-4-3-2那我现在只需要把节点 1 接在最后面也就是让2-next指向1让1-next指向nullptr。所以那两行看起来很诡异的代码就好理解了head-next-next head; // 把当前节点接到已反转链表的末尾 head-next nullptr; // 当前节点变成新的尾节点很多人搞不懂为什么递归没有显式保存前驱节点。其实递归帮我们隐式保存了调用栈每一次递归调用都停留在原链表的某一个节点上等更深层的递归返回后当前层的head就是前一层节点的“下一个节点”这种信息在递归栈里天然保留着。递归写法的时间复杂度也是 O(n)但空间复杂度是 O(n)因为递归深度是 n。面试时如果只追求过题两种写法都可以但如果链表特别长比如几万个节点递归可能爆栈迭代更稳妥。2.3 反转链表最容易踩的三个坑第一个坑是循环条件写错。有人写while (cur-next)这样最后一个节点永远不会被处理或者处理完最后一个节点之后cur变成nullptr再访问cur-next直接段错误。正确写法是while (cur)。第二个坑是忘记处理空链表和单节点链表。虽然while (cur)循环对空链表天然成立返回nullptr但如果你写的是递归版本终止条件漏了head-next nullptr单节点链表会直接死循环。第三个坑是迭代版里pre和cur的移动顺序错了。一定要先在cur-next pre改变指针之后再移动pre和cur。如果先把cur移走原链表后半段就丢了。3. 合并两个有序链表LeetCode 21哨兵节点的胜利3.1 为什么合并链表要先解决“头节点不确定”的问题题目将两个升序链表合并成一个新的升序链表。比如1-2-4和1-3-4合并结果是1-1-2-3-4-4。新链表的节点来自两个原链表不额外分配节点。最直观的思路是用两个指针分别指向两个链表的头谁的值小就把谁接到新链表上然后移动对应指针。但这里有一个尴尬的问题新链表的第一个节点是谁在循环开始前我们并不知道两个链表的最小节点是l1还是l2。如果先比较一次再决定谁是头节点代码会多一个分支而且后续循环里还要重复处理头节点。万一两个链表都是空链表头节点还不存在。解决这个问题最优雅的办法就是哑节点dummy node。先创建一个值为任意值通常 0 或 -1的虚拟节点让新链表从它开始“生长”最后返回dummy-next就行ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }这段代码里最关键的一行是tail-next l1 ? l1 : l2。循环结束意味着至少有一个链表走完了剩下的链表直接挂在tail后面即可。不需要再写循环去一个个接因为剩下的链表本身就是有序的。我见过一些同学在这里写while (l1) { tail-next l1; ... }虽然也能过但明显多写了代码。直接用三元表达式接剩余部分是这道题里很典型的“少即是多”。3.2 递归版本逻辑更短但要注意栈空间合并两个有序链表的递归写法非常简洁ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }递归的思维模型是每次只解决“当前最小的节点是谁”然后把这个节点的next指针交给递归去处理。终止条件是其中一个链表为空直接返回另一个。但这个版本有一个在实际项目中不能忽略的问题空间复杂度 O(n)其中 n 是两个链表的总长度。LeetCode 上链表长度通常不会太大递归没问题。但如果你在嵌入式环境、或者栈空间受限的场景下写代码这个写法就有风险。我自己的习惯是本地刷题用迭代版因为能顺便练哑节点这个技巧如果面试被要求写简洁版本再切换到递归。两个版本都得会写因为面试官可能会让你比较两者的优劣。3.3 合并操作的一个关键认知这道题本质上没有新建节点只改变了节点之间的连接关系。所以空间复杂度是 O(1)迭代版这一点是很多初学者容易忽略的。你合并之后的链表并没有复制一份原链表而是把原有节点重新串了一遍。如果在实际业务中合并操作可能影响原始链表的结构那需要先确认是否允许破坏原数据。另外这道题是后面“合并 K 个升序链表”的基础。如果你直接用两两合并的思路去做 K 条链表的合并时间复杂度会退化到 O(k^2·n)。到时候需要引入优先队列或分治法这里先埋个伏笔。4. 删除链表的倒数第 N 个结点LeetCode 19双指针的经典应用4.1 两趟扫描的思路先算长度再删除题目要求给你一个链表删除链表的倒数第 n 个结点返回链表的头结点。进阶要求是尝试一趟扫描完成。最朴素的思路是两趟扫描第一趟统计链表长度len那么倒数第 n 个节点就是正数第len - n 1个节点。第二趟找到它的前驱节点执行删除操作。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode* cur dummy; int len 0; while (cur-next) { len; cur cur-next; } cur dummy; for (int i 0; i len - n; i) { cur cur-next; } cur-next cur-next-next; return dummy.next; }注意这里我已经用上了哑节点。为什么因为如果要删除的是头节点即n len没有哑节点时你必须特判让head head-next。有了哑节点删除头节点也变成了统一的cur-next cur-next-next少一个分支代码不容易出错。两趟扫描的时间复杂度 O(n)空间复杂度 O(1)已经可以接受。但题目明确提到“尝试使用一趟扫描实现”这就是考察双指针的地方了。4.2 一趟扫描快慢指针的精妙之处一趟扫描的思路是这样的让fast指针先走 n 步然后slow指针和fast指针一起走。当fast走到链表末尾fast nullptr时slow恰好指向倒数第 n 个节点的前驱。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode dummy(0); dummy.next head; ListNode* fast dummy; ListNode* slow dummy; for (int i 0; i n; i) { fast fast-next; } while (fast-next) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy.next; }这里有一个很多人第一次看会困惑的点为什么fast要先走 n 步而不是 n-1 步原因是slow最终要停在待删节点的前一个位置而不是待删节点本身。fast先走 n 步之后fast和slow之间的距离是 n。当fast走到最后一个节点fast-next nullptr时slow距离链表末尾正好还差 n 个节点也就是说它站在倒数第 n1 个节点的位置也就是待删节点的前驱。换个角度理解如果fast先走 n-1 步那slow最后会停在待删节点本身。想删除它还得额外用一个prev变量保存前驱反而更麻烦。先走 n 步的设计直接省掉了前驱变量。注意while (fast-next)而不是while (fast)。这决定了slow是停在待删节点的前驱还是待删节点本身。我见过有同学用while (fast)最后slow指向的是待删节点删除逻辑就乱了。4.3 边界条件n 的合法性处理这道题的边界条件主要看 n 是否合法。题目通常保证 n 不会超过链表长度所以不需要考虑n len的情况。但如果实际工程中遇到这种输入建议先做一次长度检查或者加保护。还有一种常见情况是删除唯一节点。链表只有一个节点n 1。用哑节点方案fast先走一步然后while (fast-next)不会进入循环fast已经是最后一个节点slow不动接着执行slow-next slow-next-next也就是让dummy-next nullptr。返回dummy.next也就是nullptr结果正确。为什么这道题我强烈推荐哑节点因为删头节点和删唯一节点两种边界在没有哑节点的情况下都需要额外写分支。哑节点把所有情况统一了这就是它的价值。5. 环形链表 I 与环形链表 II快慢指针与数学推导5.1 判断是否有环LeetCode 141快慢指针为何是 O(1) 空间最优解题目给你一个链表的头节点判断链表中是否有环。要求空间复杂度 O(1)。最容易想到的办法是用哈希表记录访问过的节点但空间复杂度是 O(n)。快慢指针可以把空间降到 O(1)bool hasCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }慢指针每次走一步快指针每次走两步。如果链表无环快指针会先走到nullptr循环自然结束如果有环快指针会在环里追上慢指针此时两个指针指向同一个节点。有一个细节值得琢磨为什么快指针每次走两步而不是三步、四步两步保证了在环中追赶时不会出现“跳过”优雅的数学性质。如果步长和环的周长有公约数可能出现快指针一直在慢指针前面绕圈、永远不相遇的尴尬情况。两步是最稳妥、最经典的选择。面试时如果被追问能答出“两步保证追击过程不会错过”这一点会加分不少。另一个细节是循环条件。while (fast fast-next)同时判断了fast和fast-next防止访问空指针。如果链表是空链表或者只有一个节点fast本身或者fast-next为nullptr循环不会进入返回false正确。5.2 寻找环入口LeetCode 142相遇之后再走一圈的数学推导环形链表 II 在 141 的基础上多了一个要求不仅要判断有没有环还要返回环的入口节点。如果无环返回nullptr。经典解法分成两步第一步用快慢指针判断是否有环并找到相遇点。 第二步把慢指针重置到头节点然后再让慢指针和快指针以相同速度前进两者第二次相遇的位置就是环入口。代码是这样的ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } if (!fast || !fast-next) return nullptr; slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }很多人能背下这段代码但真正追问“为什么第二次相遇在入口”时就卡住了。我自己第一次学的时候也卡了很久后来画图画了整整一页纸才想明白这里把推导过程完整写下来。设链表头到环入口的距离为 a环的周长为 b。慢指针入环后走了 x 步与快指针相遇。那么当它们相遇时慢指针走的总路程a x快指针走的总路程a n·b x其中 n 1表示快指针已经在环里多绕了 n 圈因为快指针速度是慢指针的两倍所以快指针的路程是慢指针的两倍a n·b x 2(a x)化简a n·b - x (n - 1)·b (b - x)这个式子说明了什么b - x是相遇点继续往前走到环入口的距离。等式右边表示从相遇点出发走(n-1)整圈再走(b-x)步会到达环入口。而左边是一个从头节点出发、走了 a 步的指针它恰好也到达环入口。所以当两个指针以相同速度分别从头节点和相遇点出发时它们必然会在环入口相遇。这就是代码里第二次while (slow ! fast)循环的数学依据。如果 n 1那么 a b - x也就是从头节点到环入口的距离等于从相遇点回环入口的距离两个指针同时到达如果 n 1从相遇点出发的指针会多绕几圈但最终仍然在环入口相遇。5.3 环形链表 II 的三个常见误区第一个误区把相遇点误当成入口。从推导可以看出相遇点是慢指针入环后走 x 步的位置只有极巧合的情况下 x 才等于 b/2也就是入口。绝大多数情况下相遇点不是入口直接返回fast会错。第二个误区忘记检查无环的情况。如果链表无环第一步的循环结束后fast或者fast-next是nullptr你不检查就直接执行slow head的第二步逻辑会进入死循环或访问空指针。迭代代码里if (!fast || !fast-next) return nullptr;这一行不能省。第三个误区第二步中两个指针的速度不统一。重置slow head之后两个指针必须每次各走一步。如果还让fast走两步两个指针不一定会在入口相遇甚至可能在环里绕很多圈之后才碰上运气不好还会死循环。6. 做题过程中的高频 bug 与调试技巧实录6.1 链表题最常见的三类 bug第一类是空指针访问。典型场景是忘了判断head nullptr或者在while循环里访问了nullptr-next。这类 bug 在本地环境里表现为段错误在 LeetCode 上表现为直接爆内存错误。解决办法是写循环条件前先问自己一句当前指针可能为空吗如果可能为空循环条件里就必须包含对它的判空。第二类是指针丢失。典型场景就是反转链表时没有先保存next就修改cur-next结果链表后半段全部丢失程序进入死循环或者输出错误结果。这类 bug 往往隐蔽因为代码看起来逻辑没错但运行结果就是不对。排查方法就是打印链表看每次操作后的内容是否符合预期。第三类是边界条件处理错误。删除倒数第 N 个节点时n len的情况删除唯一节点时链表变空的情况环形链表中只有一个节点自环的情况。这些边界条件如果不提前列出来很容易漏掉。我自己的习惯是不管什么链表题先在心里过一遍空链表、单节点链表、两个节点链表这三种基本用例再开始写代码。6.2 三种实用的调试方法第一种是打印法前面已经提过。我用得最多尤其是反转链表和合并链表打印函数能看到每一步操作后链表的形态能快速定位到是哪一步出了问题。第二种是画图法。注意这里的画图不是面试时在纸上边讲边画给面试官看而是自己在草稿纸上模拟指针变化。环形链表 II 的数学推导我就是在纸上画了几遍才真正理解。对于指针操作多的题画图比任何调试器都好用因为链表的内存结构在脑内模拟很容易出错。第三种是小用例法。不要一上来就用长链表测试那是浪费时间。空链表、单节点、两个节点、三个节点、带环的链表每个用例跑一遍基本能覆盖所有边界问题。LeetCode 上有些题目的Testcase里就有很长的链表遇到报错可以直接在本地用最短的复现用例来调试效率高得多。还有一个跟链表题相关的内存问题要提用 C 刷题如果自己new了节点比如复制链表、构造新链表时LeetCode 环境会自动回收但在本地测试或者工程代码里你需要手动管理内存。尤其是删除节点和反转链表的变体题目建议加上delete来释放不再使用的节点避免内存泄漏。这一点写小 demo 的时候不致命但在真实项目中是基本功。6.3 从这五道题里提炼出的链表通用方法论刷完这五道题我最大的体会是链表题的核心不在“会用-next”而在于建立几种固定的思维范式。第一凡是涉及头节点可能变化的操作比如删除头节点、反转链表、插入到头部优先考虑用哑节点。哑节点把“头节点可能变化”的问题消解掉了所有节点都一视同仁地通过prev-next来操作。我后面刷“删除排序链表中的重复元素 II”这类题时也是这个思路。第二凡是需要同时维护前驱、当前、后继三个位置的用三指针。反转链表是典型例子需要pre、cur、next三个指针协作。这种三指针范式也可以用在中点删除、两两交换节点等问题上。第三凡是涉及倒数第 k 个节点、求中点、判断环这一类问题优先考虑快慢双指针。倒数第 N 个节点是快指针先走 n 步求中点是快指针走两步慢指针走一步判断环也是快慢指针。这套路一旦熟练很多题的解题方向会立刻清晰。第四写代码之前先在草稿纸上画出指针指向变化。不是所有题都需要画但反转链表和环形链表 II 这两题我强烈建议画。画完再写代码思路快且不容易错。7. 后续还可以怎么扩展链表专题上就到这里了。其实 Hot 100 里的链表题还有很多比如合并 K 个升序链表、K 个一组翻转链表、排序链表、相交链表、复制带随机指针的链表。这些题的底层技巧大部分都能从今天这五道题里延伸出来。比如合并 K 个升序链表核心还是今天“合并两个有序链表”的思路只是需要引入优先队列或者分治策略K 个一组翻转链表核心还是“反转链表”的三指针法只是多了分组和区间翻转的边界处理相交链表则用到双指针的另一种用法让两个指针分别走完自己的链表后再走对方的链表最终在相交点相遇。我个人建议刷完这几题之后再去做“两数相加”“两两交换链表中的节点”“旋转链表”这些变形题把今天讲的哑节点、双指针、指针反转这几个工具反复用几遍。这些工具用得越熟后面遇到再复杂的链表题你也不会慌。最后分享一个小技巧链表题做完之后一定要试着用另一个方法再写一遍。反转链表用迭代写完了再用递归写一遍合并有序链表用递归写完了再用迭代写一遍。同一个题目用两种方法各做一次你的理解深度会明显不一样这也是我从这五道题里收获最大的一个习惯。