链表题在算法训练里一直是“看了解析觉得很简单自己一写就卡住”的重灾区。评论区最常见的一句话就是“我懂了但是代码就是写不对。” DAY4这四道题——两两交换节点、删除倒数第N个节点、链表相交、环形链表II——表面上是四个独立题目实际上都在反复敲打同一组核心技能虚拟头节点的使用、双指针的移动节奏、以及指针重连时的先后顺序。如果你把这四道题当成孤立题目死记硬背那过两周大概率全忘光如果能看穿它们共享的底层逻辑这四道题就是一次很集中的“链表双指针强化训练”。这篇文章我按自己刷题时的思考路径来讲不直接贴标准答案而是重点拆解每道题“为什么这么做”“哪里容易写错”“画图时应该注意什么”。无论你是刚开始刷链表还是已经刷过几遍想查漏补缺都应该能从里面拿到点东西。1. 四道题为什么适合放在同一天链表题的本质是双指针叙事1.1 链表的操作共性虚拟头节点思维先说说为什么DAY4集中刷链表。算法训练营的题目编排不是随机的这四道题有一个共同特征它们都不是对链表做简单的遍历而是需要改变链表结构或者在特定位置停下来做操作。两两交换节点要改指针方向删除倒数第N个节点要找到目标节点的前驱链表相交要求某个位置做比较环形链表II则依赖两个指针的追击关系。这些操作绕不开一个问题头节点可能被修改而头节点没有前驱。遇到“头节点可能被改”的题虚拟头节点dummy node是标配解法。它的逻辑很朴素在原链表前面额外挂一个节点让头节点拥有和前驱一样的待遇这样所有节点的删除、插入、交换操作都能统一用一套逻辑处理不用单独给头节点写if分支。ListNode* dummy new ListNode(0); dummy-next head;就这么三行能省掉后面一大堆边界判断。我在两两交换和删除倒数第N这两道题里都用了它实测下来代码可读性和正确率都会明显提升。1.2 双指针场景快慢指针和间距指针的本质这四道题里出现了一组“同源变体”快慢指针。环形链表II用一快一慢来检测环删除倒数第N用一前一后拉开固定距离链表相交本质上也是让两个指针到达同一起跑线再同步前进。它们的核心思想相通都是通过控制两个指针的相对速度或相对位移让某些信息在一次遍历中就能确定下来。很多人学到这里会困惑为什么不让链表支持随机访问为什么不能直接算长度再定位因为链表节点在内存中是离散的只有next指针串联没有下标概念。双指针技巧正是为了弥补“无法随机访问”这个短板——你不是不知道倒数第N在哪吗那就让一个指针先走N步然后两个指针同步挪前一个到底后一个自然就到目标位置了。这就是用“相对位置”替代“绝对位置”的典型思路。有了这层理解四道题就不再是四个孤立的模板而是一套思维框架下的四个应用场景。下面逐题拆。2. 两两交换节点先画图再写码比背套路可靠十倍2.1 题意与递归解法的思维路径题目要求把链表中相邻节点两两交换比如1-2-3-4变成2-1-4-3。注意题目说的是交换节点不是交换节点里的值。虽然有些用例用交换值也能过但面试官考察的是你对指针操作的理解按值交换属于投机取巧不推荐。我第一次做这道题时先写了递归版本因为它的递归结构非常直观。ListNode* swapPairs(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead head-next; head-next swapPairs(newHead-next); newHead-next head; return newHead; }递归的思路是每次只看两个节点把第二个节点提为这一小段的头然后递归处理后面剩下的链表。终止条件就是“没有节点或者只剩一个节点”时不需要交换。这个写法很优雅但如果你对递归不熟建议还是掌握迭代版本——很多后续题目用递归反而会增加理解负担。2.2 迭代解法的指针重连细节迭代版本也是我最终推荐面试用的版本因为它的状态转移清晰、不会出现递归栈溢出的隐患。核心思路需要三个指针一个指向前一组交换完的末尾pre两个指向当前要交换的节点first和second。ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; while (pre-next ! nullptr pre-next-next ! nullptr) { ListNode* first pre-next; ListNode* second first-next; ListNode* third second-next; // 关键先保存第三节点 pre-next second; second-next first; first-next third; pre first; } ListNode* result dummy-next; delete dummy; return result; }这里最容易被忽视的一行是ListNode* third second-next;。为什么要先保存它因为一旦执行second-next first原来second指向的链表剩余部分就断开了。如果不先把下一个节点存下来后面的节点就找不到了。这种“先保存后继再改指针”的习惯是所有链表指针操作中最重要的经验之一。2.3 高频易错点循环条件与指针移动时机循环条件写的是pre-next和pre-next-next都不为空。因为每次交换的是两个节点少一个都不成对。奇数长度的链表最后一个节点会保持原样这符合题意。pre的移动时机交换完成后这一段新的“末尾”是first原来的第一个节点换完排在后面下一组要接在它后面。所以pre first不是在循环开始时更新。如果链表为空或只有一个节点dummy-next会直接指向原链表头while条件不满足返回的就是原链表逻辑上完全正确。我见过很多人没画图直接写结果把first-next third写成了first-next pre链表当场变成环。链表题的bug几乎都是指针乱指导致的所以我的习惯是先画一张“交换前的链表状态”标好每一步的指针目标再照着图写代码。3. 删除倒数第N个节点窗口滑动思路的边界推演3.1 两次遍历为什么不够好删除倒数第N个节点最朴素的做法是遍历一次求长度然后第二次遍历找到正数第len-N1个节点做删除。这个方法能过但面试时会被追问“能不能只遍历一次”。只遍历一次的核心难点在于你不知道链表总长多少但你又想定位倒数第N个。这时候快慢指针就登场了。让快指针先走N步然后快慢一起走。当快指针走到链表末尾时慢指针恰好指向倒数第N个节点。这个方案的时间复杂度是O(n)空间复杂度O(1)是面试官想看到的答案。3.2 快慢指针相差N步的实现这里有个细节我们要删除倒数第N个节点实际操作时需要操作它的前驱节点而不是节点本身。所以慢指针应该停留在“倒数第N个节点的前一个位置”。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* fast dummy; ListNode* slow dummy; // fast先走n步 for (int i 0; i n; i) { fast fast-next; } // fast和slow同步前进直到fast到达最后一个节点 while (fast-next ! nullptr) { fast fast-next; slow slow-next; } // slow-next就是要删除的节点 ListNode* target slow-next; slow-next target-next; delete target; return dummy-next; }这里有两个容易踩的坑第一fast和slow的初始位置。很多版本把fast初始化为headslow初始化为head也能做但要额外处理“删除头节点”的情况。我习惯让fast和slow都从dummy出发逻辑更统一。第二循环条件为什么是fast-next ! nullptr而不是fast ! nullptr。如果写成后者fast走到nullptr时slow就指向倒数第N个节点本身而不是它的前驱。我们要做的是删除所以必须让slow停在目标节点的前一个位置。从dummy出发fast先走n步那么当fast指向链表最后一个节点时slow和fast之间差n步slow恰好是倒数第N个节点的前驱。这个条件值得好好体会。3.3 虚拟头节点在删除场景中的特殊价值这题还有一个关键场景删除头节点。假设链表1-2-3要删除倒数第3个节点也就是节点1。如果没有dummy你需要单独判断head是不是目标节点然后head head-next逻辑会分叉。有了dummy之后删除头节点就和其他节点完全相同slow指向dummyslow-next指向head执行slow-next slow-next-next返回dummy-next即为新的头。这个统一性正是虚拟头节点存在的意义。3.4 极端用例的推演n等于链表长度fast从dummy走n步后指向链表末尾的节点此时fast-next是nullptr直接跳过while循环slow还在dummy删除的是头节点。正确。链表只有一个节点fast走1步到NULLslow在dummy删除dummy-next正确。n非法大于长度或等于0题目一般会限定n有效但如果你自己写工具函数记得加异常处理。这类边界推演在面试中很加分因为很多人写出来“感觉对”但说不清为什么对。能把极端情况一条条列出来说明你是真的理解了。4. 链表相交从“同一起跑线”反推指针设计4.1 题意的准确解读交点不是值相等面试题02.07链表相交最常被误解的地方是相交的定义。题目说的相交不是两个节点的val相等而是两个链表存在一个公共节点对象——从某个节点开始之后的所有节点都完全相同。也就是说问题本质是找两个链表在内存中第一次重合的位置。你可以这样理解两个链表就像两条路一旦在某处汇合成同一条路后面就再也不会分叉了。因为每个节点的next只有一个方向不可能走到某处发现“这条路又分成两半了”。既然相交之后完全重合那么两个链表在交点之前的部分长度可能不同。比如一个链表长5另一个长8交点可能在长链表第4个位置短链表第3个位置。如果两个指针各自从头开始走它们永远不可能“同时”走到交点因为起点到交点的距离不同。4.2 对齐思想的实现方式解法很自然先把两个链表“对齐”。让较长的链表指针先走两个链表的长度差然后两个指针同步前进第一次指向相同节点时就是交点。ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA getLength(headA); int lenB getLength(headB); ListNode* pA headA; ListNode* pB headB; int diff abs(lenA - lenB); if (lenA lenB) { while (diff--) pA pA-next; } else { while (diff--) pB pB-next; } while (pA ! nullptr pB ! nullptr) { if (pA pB) return pA; pA pA-next; pB pB-next; } return nullptr; } int getLength(ListNode* head) { int length 0; while (head ! nullptr) { length; head head-next; } return length; }这个思路的关键在于“两个指针从同一起跑线出发同步速度必然在交点相遇”。如果不存在交点两个指针会同时走到nullptr返回NULL。4.3 更进一步的解法循环交错双指针前面这个方法要先求长度代码略长。还有一个技巧性更强的写法pA走完链表A之后从链表B的头开始继续走pB走完链表B之后从链表A的头继续走。这样一来两个指针走过的总路程都是lenAlenB。如果存在交点它们会在交点处相遇如果不存在它们会同时走到nullptr。我第一次看到这个解法时觉得像是魔术后来想明白了这本质上是把两个链表的长度差异“分摊”到两次遍历中达到对齐效果。不过这个写法虽然简洁面试时解释起来需要花时间。我的建议是先把长度差版本理解透如果有余力再掌握这个进阶写法两者各有适用场景。5. 环形链表II数学推导不只是为了证明更是为了写对循环条件5.1 快慢指针的相遇条件环形链表II有两个子问题第一链表中存不存在环第二如果存在找到环的入口节点。判断有没有环经典做法是快慢指针。快指针每次走两步慢指针每次走一步。如果没有环快指针会首先走到nullptr如果有环快慢指针最终会在环里相遇。这里我有一个反复强调的细节为什么快指针每次走两步而不是三步四步。走两步时快指针相对于慢指针的速度差是1步意味着每迭代一次快指针离慢指针近一步所以快慢指针必然会相遇。如果速度差大于1虽然通常也能追上但存在“跳过”慢指针的可能性绕环多圈情况下数学上更复杂没必要给自己找麻烦。5.2 入口推导过程假设从链表头到环入口的距离为a从环入口到快慢指针第一次相遇点的距离为b从相遇点继续走到环入口的距离为c。环的总长度为bc。慢指针从头走到相遇点走了ab步快指针走了abk*(bc)步其中k是快指针比慢指针多绕的圈数。因为快指针速度是慢指针的两倍所以2*(ab) abk*(bc) ab k*(bc) a k*(bc) - b (k-1)*(bc) c当k1时a c。这意味着从链表头走到入口的距离等于从相遇点继续走到入口的距离。当k1时从相遇点出发需要多绕几圈后再到入口但“一个指针从头出发、另一个从相遇点出发同速前进最终会在入口相遇”这个结论依然成立。有了这个推导代码就非常直接了。ListNode *detectCycle(ListNode *head) { ListNode* fast head; ListNode* slow head; while (fast ! nullptr fast-next ! nullptr) { fast fast-next-next; slow slow-next; if (fast slow) { // 有环找入口 ListNode* p1 head; ListNode* p2 fast; while (p1 ! p2) { p1 p1-next; p2 p2-next; } return p1; } } return nullptr; }5.3 边界情况与常见卡点这题我见过最多的卡点有两个。一是循环条件写不对。while (fast ! nullptr fast-next ! nullptr)这个条件保证fast每次都能安全走两步。如果写成while (fast ! nullptr)当fast指向最后一个节点时fast-next-next会访问空指针。没有环的链表fast会在末尾停下然后返回nullptr。二是不知道为什么要从相遇点继续走。有人把p2 fast写成了p2 slow其实相遇时fast和slow指向同一个节点两种写法都能跑通。但理解层面要清楚我们利用的是相遇点的位置而不是某个具体指针的身份。另外如果题目只要判断有没有环141题那代码更短找到相遇点直接return true即可。DAY4这题更进一步需要把入口也找出来。一次能把两道题一起解决性价比很高。6. 调试链表的实用技巧与面试延伸6.1 一个顺手但极其实用的辅助函数写链表题最容易遇到的情况是代码跑起来直接报错或者死循环超时。这些错误在本地环境往往不容易定位因为链表不像数组那样能以[1,2,3]的形式直观输出。我建议在本地练习环境里维护一个打印函数void printList(ListNode* head, int limit 20) { int count 0; while (head ! nullptr count limit) { std::cout head-val - ; head head-next; count; } if (head ! nullptr) { std::cout ... (可能环); } else { std::cout nullptr; } std::cout std::endl; }这个函数的意义在于死循环时它不会真的无限打印因为limit会截断并提示“可能环”。运行出错时你把每一步操作前的链表状态打印出来很容易定位是哪一次指针操作出了问题。6.2 常见Bug模式复盘结合这四道题我总结几类高频Bug空指针访问在链表操作中对nullptr调用-next是最常见的崩溃原因。处理办法是每次访问node-next之前先确认node ! nullptr。丢节点改指针时没有先保存后继节点导致链表的某一部分凭空消失。两两交换里的third second-next就是这个目的。循环条件写错该判fast-next ! nullptr写成fast ! nullptr导致多走一步或少走一步。删除倒数第N这题的while (fast-next)就是经典例子。删节点后没有deleteC里new出来的节点如果不手动释放会内存泄漏。刷题时不太要紧但项目里这就是事故。6.3 从这四道题出发可以继续刷什么如果你把这四道题吃透了我建议趁热打铁做几个延伸题检验一下双指针思维的迁移能力LeetCode 876 链表的中间节点快指针走两步慢指针走一步快指针到末尾时slow就是中间点。LeetCode 61 旋转链表先求长度再把链表头尾相连定位新头节点后断开。LeetCode 143 重排链表找中点、反转后半段、再交替合并。这个题目几乎综合了链表操作里所有基本功。这些题的核心操作你都能在DAY4这四道题里找到影子。链表题的练习策略不该是“每道题背一遍模板”而是“每种核心技巧练到条件反射”——看到链表题先问自己要不要虚拟头节点要不要双指针两个指针之间是速度差还是间距差。想清楚这三个问题题目就解了一大半。7. 我刷完这四道题后的几点体会这四道题在训练营里被安排在同一天确实有它的道理。它们把链表的基本功拆得很细两两交换练的是指针重连顺序删除倒数第N练的是间距双指针链表相交练的是对齐与同步环形链表练的是快慢指针与数学推导。每道题单独看都不算难但合在一起几乎覆盖了所有链表指针操作的高频考点。我自己刷的时候最深的感触是链表题不是靠脑袋想出来的是靠图画出来的。两两交换那道题我反复在纸上画了不下五遍才彻底搞明白指针重连的顺序环形链表II那道题我也是画了一遍推导图才真正理解为什么相遇点出发的指针能和头节点指针在入口相遇。如果你现在觉得吃力不要急。刷链表题就是这样前面几道题卡顿很正常量变到质变往往就在某几道题之后。VT虚拟头节点、双指针、先保存后继再改指针这三个习惯一旦养起来后面再做链表相关的复杂题你会明显感觉自己变顺了。