链表是手撕环节的头号考官。必刷题单与算法入门课共同锁定了五道题:反转链表(206)、链表判环(141/142)、合并两个有序链表(21)、找中间节点(876)、删除倒数第 N 个(19)。它们共享同一套心法——虚拟头节点、快慢指针、指针操作的防断链顺序。这一讲把五题串成一个「技能树」。
链表没有随机访问,一切操作都是指针体操。面试官想看的恰恰是指针操作的不出错能力:断链、丢节点、死循环,三个事故都在一两行代码之间。五道题十分钟内全对的候选人,基本功这一栏直接给满分。它们还是后续题的地基:回文链表=找中点+反转后半,重排链表=中点+反转+合并,LRU=双向链表操作(32.4)。
虚拟头节点(dummy,一个挂在真实头节点前的哨兵)像排队时先立一个「临时队长」:头节点可能被删除或更换的场景下,有了 dummy 就永远不需要单独处理「头变了」的分支,最后返回 dummy.next 即可。快慢指针(一快一慢两个引用同向走)像操场上的跑圈:快的每步比慢的多走一格,链表有环必然套圈相遇,无环则快者先到终点。
LeetCode 206,出场率第一。迭代三指针,注意先存后断的顺序:
public ListNode reverse(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next; // 1. 先保住后继,否则断链
cur.next = prev; // 2. 反转当前指针
prev = cur; // 3. prev 前进
cur = next; // 4. cur 前进
}
return prev; // cur 为 null 时 prev 恰是新头
}
四步顺序是防断链的全部:先 1 后 2,一旦先反转再取 next,后半段链表就永远丢了。
判环与环入口(141/142):快慢指针相遇则有环;找入口用 Floyd 结论——相遇后一个指针回到头,两指针同速前进,再次相遇处即入口。证明思路:设头到入口 a 步、入口到相遇点 b 步,快者走了 a+b+c(c 为相遇点绕回入口),由速度两倍关系 a+b+c = 2(a+b) 推出 a = c。合并有序链表(21):dummy 起步,双指针取小结点接到结果尾,一个走空后直接拼另一条剩余段。找中间节点(876):慢一步快两步,快到尾时慢在中点——偶数长度时慢指向中间两个的后一个,要主动说明这个约定。删除倒数第 N(19):快指针先走 n+1 步,再快慢同速,快到尾时慢的下一格就是待删节点——一遍扫描替代「先数长度再走」的两遍。五题共享一个默念口诀:改指针前先存后继,边界想清楚空表与单节点。
21 合并两个有序链表是「dummy+双取小」的标准形态:
ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next; // 尾指针始终指末位
}
tail.next = (a != null) ? a : b; // 剩余段 O(1) 拼接
return dummy.next;
}
三个细节值钱:相等时取 a 保稳定;剩余段直接拼接不逐个复制;追问「N 个链表合并(23)」答小顶堆 O(N log k) 或分治两两合并——把本题当积木。再看删除倒数第 N 个(19)的快慢间距版:
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy, slow = dummy;
for (int i = 0; i <= n; i++) fast = fast.next; // 先走 n+1 步
while (fast != null) { fast = fast.next; slow = slow.next; }
slow.next = slow.next.next; // slow 恰停在被删节点的前驱
return dummy.next;
}
fast 先走 n+1 步(从 dummy 起)保证 slow 停在前驱而不是待删节点——差一步的边界就是这题唯一考点。纸上调试法(链表题自检神器):画三个节点加 dummy,把代码每步的指针变化逐一画出来——先存后继是否守住、尾指针是否推进、空表是否第一行拦截,纸上跑一遍胜过脑内模拟十遍。现场先说「我用 a b c 三个节点走一遍」再动笔,通过率显著提高。追问链还有两问常挂尾:为什么用 while 不用 for——长度未知,null 是唯一终点;ArrayList 与 LinkedList 怎么选——随机访问选前者、头尾插删选后者,但真实工程里数组的缓存友好性几乎总是赢家(第 4.3 讲拆过),把答案从背诵升维到工程判断。五连练完还有个组合彩蛋:回文链表(234)=找中点+反转后半+逐一比对,三题拼一道,出现的频率不低于五连本身——答法就是「先报拼装方案再动手」,组合意识是练完五连的自然产物。
反转链表有个家族:区间反转(92,反转 left 到 right 之间)在整体反转上加「入口定位」——走到 left 前一个节点记作新 dummy,套路完全复用;K 个一组翻转(25,Hard 但高频)=分组定位+组内反转+组间缝合,面试出现时先报「分组递归」思路再动手。家族的存在说明:反转这题练的不是一道题,是「指针操作的乐高能力」。快慢判环还有一笔数学账要当场算得清:为什么相遇前慢指针不会在环里被反复套圈套到无穷——快指针每轮比慢的多走一格,距离每轮缩短一,从任何初始距离追到零最多一圈,「每轮缩短一」四个字就是不会错过的证明;而「为什么相遇后一个回起点同速走必在入口相遇」,用 a(头到入口)、b(入口到相遇点)、c(相遇点绕回入口)三个变量列方程,上一节已推过——两笔账备齐,判环这题的追问就封顶了。
链表五连共享两个技巧——dummy 哨兵与快慢指针,练熟它们的标准顺序「先存后继再改向」,五道高频题就是同一道题的五种变奏。