连着刷到链表专题的第四天今天一口气做了四道题第24题两两交换链表中的节点、第19题删除链表的倒数第N个节点、一道面试常考的链表相交题以及第142题环形链表II。四道题里三简单一个中等偏难但做完你会发现它们全在考同一件事——正确处理链表节点的指针关系。适合正在跟算法训练营的人、准备面试的以及链表操作老是空指针的同学。这四道题不是四个孤立的知识点而是把链表操作里的三类核心能力放在一起练改指针结构、用双指针、做简单数学推理。第一题是纯粹的结构修改考验断链顺序第二题是双指针的标准应用第三题需要你先搞清楚“相交”的语义第四题是快慢指针加一圈数学推导。也就是在今天的训练里如果能把四道题全部手写出来链表的基础操作基本就过关了。从做题顺序上说我建议按题目顺序来不要直接跳难的。两两交换先把“改指针结构”的手感练出来再去做双指针大脑会更适应。第四题是今天的难度天花板你如果一上来就磕它多半会被绕晕。1. 第四天训练内容全景拆解1.1 四道题隐藏的共同主线先说主线。第一题两两交换核心是“在断开旧链接之前先保存后继节点”第二题删除倒数第N个节点核心是“用两个指针保持固定步距”第三题链表相交核心是“对齐两个链表的尾部再逐节点比较”第四题环形链表II核心是“用快慢指针的相遇关系反推入口”。看起来每一题都在讲不同的东西但在代码里你都会反复用到三个动作声明虚拟头节点、用临时变量接住即将丢失的节点、在while循环里判断next是否为空的边界。另一个隐藏的共同点是它们都特别容易在边界条件上出错。单节点链表、只有两个节点、链表为空、倒数第N个刚好是头节点……这些情况只要少判断一次程序就会直接报空指针。刷完这四道题再回头看边界题错的往往不是思路而是细节。1.2 虚拟头节点到底解决了什么问题关于虚拟头节点很多第一次接触的同学会问为什么要多造一个节点出来直接操作head不行吗直接操作head会遇到两个麻烦。第一个麻烦是如果头节点本身就要被删除或者被换位置那么返回值没法统一。比如删掉倒数第N个节点时如果删的正好是头节点head就不再是原来的head了你得特判“如果删的是头节点就返回head.next”这类特判用多了特别容易漏。第二个麻烦是在链表开头新增节点时插入逻辑和中间插入逻辑不一致代码要多写一个分支。用一个虚拟头节点dummy让dummy.next始终指向真正的头所有操作都在dummy后面做最后统一返回dummy.next。这样处理头节点的情况和中间节点完全一样既不用特判也不容易拿错指针。我在做题时几乎把加dummy当作固定动作凡是可能影响头节点的操作我都会先加一个dummy。这不是偷懒而是把容易出错的分支直接消掉。注意在C/C里自己new虚拟头节点的话函数结束前记得delete避免内存泄漏用Java的话交给GC处理不用操心。刷题时我偶尔会忘但在工程代码里这是必须养成的习惯。2. 两两交换链表中的节点练的是“断链顺序”第24题要求把链表两两交换比如1-2-3-4变成2-1-4-3。题目看起来很简单但非常挑动手能力。我第一次手写直接卡在“到底先让谁指向谁”上。2.1 思路与指针命名我用三个指针来干这件事。设pre是当前要交换的两个节点的前一个节点p是第一个节点q是第二个节点nxt是q的下一个节点。核心步骤就四步pre.next指向qq.next指向pp.next指向nxt把pre移动到p上准备处理下一对。这个顺序看起来很清晰但这里有个细节如果先把q.next指向p然后才想起来要保存nxt此时nxt已经丢了——因为p.next已经被改成了q原来p后面的nxt就再也找不回来了。所以动手前的第一件事永远是把nxt先存下来或者在不改变原链表前就把所有需要用的引用读清楚。用一句大白话总结先把2从1后面摘出来接到pre后面再让2指向1再让1指向3。每一步都是在“旧连接断开之前先把新连接建好”。2.2 代码实现与边界这里给一段Java实现供你照着跑public ListNode swapPairs(ListNode head) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; while (pre.next ! null pre.next.next ! null) { ListNode p pre.next; ListNode q pre.next.next; pre.next q; p.next q.next; q.next p; pre p; } return dummy.next; }这段代码里交换的顺序被我写成pre.next qp.next q.nextq.next p。和刚才说的四步法不完全一样但效果相同因为我在换之前先把p和q两个引用取了出来所以顺序可以微调。这就像搭积木只要先把所有要移动的积木块拿在手里后面怎么摆都不会乱。边界条件只判断两种情况pre.next为空时链表为空或已经到末尾pre.next.next为空时只剩一个节点不需要再交换。这两个条件写成while条件后整个方法非常顺节点少到不能再少的情况都被覆盖了。2.3 三个易错点这道题我踩过的坑主要有三个。第一个是忘记把pre移动到交换后的第二个节点上。如果交换完不更新pre下一次循环还会用同一个pre结果就会把已经交换过的部分再换回去轻则死循环重则链表结构被彻底打乱。第二个是误以为交换完头节点后最后要返回head。实际上head节点此时已经不是新链表的头了正确做法是返回dummy.next。如果你返回的是原来的head输出的链表会丢节点而且丢的还不是末尾的节点排查起来相当痛苦。第三个是用pre.next.next或pre.next.next.next时没看清层级。在Java里这种连续取next的写法很容易手滑一旦中间有一个节点是null直接抛空指针。我的习惯是像代码里那样先取出p和q再通过变量名操作避免长链式访问。3. 删除倒数第N个节点双指针的一次经典应用第19题要求在单链表里删除倒数第N个节点并要求尽量一次完成遍历。这是双指针里“快慢指针”的经典场景也是链表双指针的入门题。3.1 为什么双指针能一次遍历如果你不知道链表的长度常规做法是先遍历一遍数长度再走len - n步定位到目标节点这需要扫描两遍。双指针的思路是让快指针先走n步然后快慢指针一起走当快指针到达末尾null时慢指针正好指向倒数第N个节点的前一个节点。这样总体只需要扫描一遍。为什么会有这个效果因为快指针比慢指针超前n个节点那么当快指针走到末尾null时快慢之间的距离正好是n也就是说慢指针的下一个节点就是倒数第N个节点。这个思路在很多链表题里都会复用比如找链表的中间节点也是快指针走两步、慢指针走一步等到快指针结束慢指针刚好在中间。单独看代码它就两段逻辑快指针先走n步然后while循环里快慢一起走。很简单但恰恰是这种简单的题目最考验你对“走了几步”的理解。3.2 完整实现与快指针步数解释先给代码public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode fast dummy; ListNode slow dummy; while (n-- 0) { fast fast.next; } while (fast.next ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }这里有个容易搞混的细节快指针走了n步之后第二个while的循环条件是fast.next ! null不是fast ! null。因为我们要让slow停在要删除节点的前一个节点所以要保证快指针最后停在最后一个节点而不是null。如果条件是fast ! nullslow最后会指向倒数第N个节点本身删除就得多写一步记录前驱不如直接停在它前一个节点方便。另外注意快慢指针都从dummy出发。为什么不从head出发因为当n等于链表长度时要删除的是头节点如果从head开始走慢指针会停在头节点的前一个“空位置”这正好需要一个虚拟节点来承接。用dummy后这种特殊情况被完全吸收掉了代码不用特判。3.3 面试中常见的追问这道题在面试里常被加码。第一个追问是如果只能遍历一遍怎么做答案就是双指针。如果允许两遍遍历也不用慌先求长度再找位置代码反而更直白。第二个追问是请你解释为什么快指针先走n步而不是n-1步因为我们要让快慢指针之间隔着n个节点快指针先走n步后两者之间的节点数正好是n减1距离差为n。走到最后慢指针指向倒数第N个的前驱效果刚刚好。如果把n-1写进去很可能删成了倒数第N减一个。第三个追问是链表长度小于n怎么办题目一般保证n合法但工程里必须校验。如果不校验快指针先走时就可能直接空指针。应对方法是先判n的范围或者先统计长度。面试时能主动提到这一层通常会有加分。提示删除节点后被删除的节点如果没有其他引用Java里会被GC回收但如果是C记得释放内存。刷题时一般不要求但面试官可能会顺带问一句“怎么释放”这时候能答出来会很加分。4. 链表相交比较的是“地址”不是“值”第三道题来自某次面试题集原描述是判断两个链表是否相交并返回相交的第一个节点。相交的定义是两个链表从某个节点开始后续所有节点都共用同一条链。4.1 相交到底指什么先澄清一个最容易出错的地方相交指的不是两个节点值相等而是节点地址相同也就是指向同一块内存。链表里经常出现两个节点的val一样但它们是完全独立的不同节点。判断相交必须比较引用Java里的C里的指针相等而不是比较节点值。用一个生活类比来解释两条道路从某个路口开始合并成同一条路这个路口就是相交点而不是说两个路牌上写的内容一样就算合并。判断路口的唯一标准是物理位置相同不是路牌内容相同。理解了这一点就会明白为什么这道题不能用哈希集合里存val来实现——如果两个链表有相同值的节点但不相交就会误判。正确做法是存节点引用/节点本身。我在网上见过不少人把这道题写成“值相等就返回”样例能过但一到自测就挂原因就是这个。4.2 尾部对齐解法与实现常规面试解法是先分别求出两个链表的长度然后让较长的链表先走差值步让两个链表尾部对齐。对齐之后两个指针一起走每一步都判断当前节点是否相同找到相同节点就返回走到null还没相遇就返回null。Java实现public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode a headA, b headB; int lenA 0, lenB 0; while (a ! null) { lenA; a a.next; } while (b ! null) { lenB; b b.next; } a headA; b headB; if (lenA lenB) { int tmp lenA; lenA lenB; lenB tmp; ListNode t a; a b; b t; } int diff lenA - lenB; while (diff-- 0) a a.next; while (a ! null b ! null) { if (a b) return a; a a.next; b b.next; } return null; }这里我做了个技巧如果A短B长就交换a和b让a指向较长的链表这样后面统一用lenA减lenB不用分开写两个分支。很多同学第一次看到会误以为交换了链表本身其实只是交换了两个人手里的指针不影响链表结构。这个技巧在很多双链表题里都能复用主要目的是减少重复代码。需要考虑的情况是两个链表都为空时直接返回null循环条件也能处理。两个链表从某个节点开始相交但相交点正好是短链表的头节点时较长链表先走差值步后两个指针会在头部对齐第一轮判断就能命中。两个链表完全重合时同样成立。这个解法的时间复杂度是O(lenA lenB)空间复杂度是O(1)是三种常规解法里空间最优的。4.3 哈希集合方案的取舍另外还有一种很直观的方案把链表A的所有节点都放进一个哈希集合然后遍历链表B第一个出现在集合里的节点就是相交点。这个方案写起来非常短时间复杂度同样是O(lenA lenB)但空间复杂度是O(lenA)。面试时如果你先说了哈希方案再补一句“但空间复杂度高可以用双指针做到O(1)”通常会让人觉得你考虑得比较全面。用哈希集合时Java里Set存的是对象引用ListNode没有重写equals和hashCode时默认用的就是地址比较所以不会出现按值误判。但如果你图省事把节点.val转成String存进集合那就掉坑里了。我见过一个同学为了调试方便在Set里存了“val:next.val”这种拼接字符串遇到两个节点值相同但后继不同的情况直接误判当场找了好久才定位到问题。5. 环形链表II快慢指针背后的数学第142题是今天的压轴题要求两件事判断链表有没有环如果有返回环的入口节点。它比“判断是否有环”多了一步所以对很多人来说真正难的是第二步。5.1 怎么判断有环先看第一步用快慢指针快指针每次走两步慢指针每次走一步如果链表里有环快慢指针一定会相遇。证明其实很简单慢指针进环后快指针已经在环里某个位置了。假设慢指针走了t步后进环此时快指针已经在环内走了2t步快指针可能在环的任意位置。由于快指针比慢指针多走一步每过一个时间单位两者的距离就缩短1。环长是m快指针最多需要追m-1步就能追上慢指针这段时间里慢指针走的步数小于m也就是慢指针在进环后转不到一圈就会被追上。所以只要在循环里等待快慢指针必然相遇。用代码实现时有个常见坑判断循环条件时如果用while (fast.next ! null)当链表无环时快指针可能因为fast为空而访问fast.next报空指针。正确写法是while (fast ! null fast.next ! null)。这个坑我今天亲手踩了一次所以单独拎出来强调一下。5.2 如何找到环的入口数学推导这是今天的重头戏。设链表头节点到环入口的距离为x在环入口处开始慢指针走了y步后快慢指针第一次相遇设环的周长为c快指针在相遇前已经在环内多走了k圈。相遇时慢指针总共走了x y步快指针总共走了x y kc因为快指针比慢指针多绕了k圈又因为快指针速度是慢指针的2倍所以2(x y) x y kc化简得 x y kc也就是x kc - y。现在从相遇点出发再走c - y步会到达环入口而从头节点出发走x步也会到达环入口。上面式子说明x kc - y把k1代入x c - y。当k1时x (k-1)c (c-y)也就是说从头节点出发走x步等价于从相遇点出发绕(k-1)圈后再走c-y步结果还是到环入口。结论就是我们只需要准备两个指针一个从相遇点出发一个从头节点出发每次都走一步它们一定会在环入口相遇。这个结论记下来代码就特别清爽。我第一次推导时在纸上画了半天没转过来弯后来把x、y、c标在图上一步一步代公式才彻底想明白。5.3 完整代码实现与边界验证public ListNode detectCycle(ListNode head) { ListNode slow head, fast head; boolean hasCycle false; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) return null; ListNode p1 head; ListNode p2 slow; while (p1 ! p2) { p1 p1.next; p2 p2.next; } return p1; }这里我用了两个阶段的写法第一阶段找相遇点第二阶段从头和相遇点同步走。也可以用另一个技巧让快指针重新指向head然后和慢指针同步走代码更简短但个人觉得两个新指针更直观不容易写乱。边界验证一下链表只有一个节点且成环时第一阶段后slow和fast都指向它hasCycle为true第二阶段p1和p2一开始相同直接返回该节点。链表只有一个节点且不成环时第一阶段结束后fast为null或fast.next为nullhasCycle为false返回null。两个情况都不需要特判。值得多想一步的是为什么快指针每次走两步而不是走三步、四步因为如果快指针走三步当环比较小时快指针可能每次都会越过慢指针两者距离的变化不是均匀地每次缩小1而是可能缩成负数甚至永远碰不上。两步是速度差为1保证每次循环都会缩小1是能稳定相遇的最简单方案。这个点面试官偶尔会追问属于加分项。6. 第四天刷题复盘常见错误与经验沉淀四道题独立过完之后把所有代码放在一起看能发现更多共性。第六节就是今天训练的复盘把高频错误、通用习惯和后续复习建议整理到一起。6.1 高频报错速查与现场修复思路为了方便以后复习我做了一个速查表把今天这四道题最容易出的问题和排查思路列在一起。问题现象通常在哪个环节排查思路NullPointerException循环条件里直接访问next检查while条件是否先判节点非空再取next输出链表少了头节点返回head而不是dummy.next头节点可能被修改统一返回dummy.next两两交换结果不变忘了让pre后移检查每轮结束后pre是否更新为交换后的第二个节点删除倒数第N个删错了快指针少走一步快指针先走n步不是n-1步相交判断返回空用equals比较val相交必须用引用/地址比较不能用值环形链表死循环快慢指针速度差不是1快指针走两步、慢指针走一步速度差保持为1detectCycle返回null但实际有环循环条件导致提前退出无环判断用fast null自查时先把代码通读一遍对照表格里的高频错误点逐一排除大多数情况都能很快定位。6.2 链表刷题的三个通用习惯刷完这四道题我给自己总结出三条通用习惯。第一凡是想修改链表结构先画图再写码。哪怕只是自认为很简单的题目在旁边把节点画出来、连线画出来再把要改变的连线标红。画完之后代码基本就是按图布线思路非常清晰。第二永远给链表操作加虚拟头节点。虽然偶尔不加也能过但加了之后所有操作统一尤其适合头节点可能被修改的场景。代价只是多一个节点收益是消除一类特判。第三循环条件里把“判空”和“取next”拆开写。比如while (fast ! null fast.next ! null)而不是while (fast.next ! null)就是为了防止快指针走完时产生空指针。这个习惯不是今天才养成的但今天四道题几乎每一道都测到了它。6.3 给后面刷题同学的一点建议如果你现在也在跟某个算法训练营或者自己在刷链表我给的建议是不要只看不写更不要只背代码。每道题都至少白纸黑字写一遍然后口头解释一遍自己的思路。能讲出来说明真的想明白了讲不出来说明还没消化。另外建议把环形链表II这道题的推导过程亲手推一遍不要满足于记住公式。面试里如果被问到“为什么两个指针会在入口相遇”你临时推导一遍比背答案要稳得多。面试官可能会故意问x、y、c这些变量怎么来的你要能用大白话把推导说清楚。今天这四道题做完链表的基本操作、双指针技巧、简单数学推理都有了扎实的练习。下一阶段再遇到链表类问题你大概率会发现自己已经有了自然的应激反应。我个人的体会是链表题最大的障碍从来不是语法而是脑子里有没有那张连接图。把图画清楚代码自然就绕不出错。