链表刷题实战：虚拟头节点与双指针技巧全解析

《代码随想录》day4这份笔记我刷完了，四个经典链表题全部拿下——24题两两交换节点、19题删除倒数第N个节点、面试题02.07链表相交、142题环形链表II。说实话，链表题看着简单，写起来全是坑，这周至少帮三个朋友debug过同样的错误：head被改动导致返回错误、循环条件写反导致死循环、交换节点时丢链。今天这篇就把这些坑一次性讲透。

这四道题覆盖了链表操作的几个核心基本功：虚拟头节点的使用、双指针的两种典型派系、临界状态的边界处理、以及如何用数学归纳法证明一个算法是对的。不论你是几个月后要面大厂，还是正在校招笔试刷题，把今天这四题吃透，链表这块就算真正入门了。我会按照我自己在LeetCode上实测的完整思考过程来讲，包括每次提交出错的log和最后的修复思路。

1. 为什么链表题"看着简单、一写就错"：先建立正确的心智模型

刷链表题最典型的场景是：拿到题目觉得很简单，指针指来指去而已，十分钟写出代码，submit之后看着错误的case陷入沉思，再加一个小时的print大法才找到bug。这个现象背后的核心原因，不是你不会写代码，而是脑子里没建立一个精确的"节点图景"。

链表和数组最大的区别在于，数组是连续的存储空间，你可以直接通过下标访问任意元素，它是一维的、静态的。而链表是离散的节点，每个节点只知道下一个节点在哪，它是链式的、动态的。操作链表的本质，就是修改节点之间的指向关系，而这个修改过程如果顺序错了，后面的节点就"找不到了"。

举个最直白的例子——两两交换节点。假设我们有 1 -> 2 -> 3 -> 4，目标是换成 2 -> 1 -> 4 -> 3。很多初学者的第一反应是"交换两个节点的值不就完了吗"，用swap(node1.val, node2.val)。这个做法在部分题目里确实可以通过，但在面试场景里通常不被接受，因为你没有展示出对链"结构"的理解。更重要的是，这个技巧在"交换整条子链"这种复杂操作里完全失效。

正确的做法是在节点层面调整指针。但问题来了：当你让1节点的next指向3之后，你还能找到2吗？答案是找不到了，除非你预先用一个临时变量把2保存下来。这就是链表操作的第一原则：修改一个指针之前，先用temp把"要断开的那个节点"留住。这条原则如果能刻进肌肉记忆里，链表题至少能少错百分之三十。

另外一个需要建立的图景是"虚拟头节点"（dummy head）。它是我认为day4这组题里性价比最高的一个技巧，没有之一。为什么需要它？因为链表中头节点是没有前驱的，当你需要删除、交换、翻转的恰恰是头节点本身时，你要处理的逻辑就和其他节点不同——比如删除头节点直接head = head.next就行，而删除中间节点得靠前驱的next来跳过它。这种"头节点特殊处理"的逻辑不仅啰嗦，还特别容易漏。

虚拟头节点的思路特别朴素：我手动造一个节点，把它放在真正头节点前面，这样dummy -> head，头节点就变成了"有前驱的普通节点"，所有的增删改都按照统一的逻辑处理完。操作完后返回dummy.next就行，这个next指向的一定是新的头节点，不管头节点是否被换掉。Day4这四道题里，两两交换节点和删除倒数第N个节点，用虚拟头节点可以让代码简洁不止一个量级。

2. 交换节点的指针操作顺序：断链之前先留住后路

两两交换节点（24题）是我刷题这么多年觉得最能训练"指针操作手感"的一道题。它不涉及复杂的算法思想，纯粹考察你能不能把三步走正确地连起来。

先说思路。在虚拟头节点的基础上，假设当前操作到cur这个节点，它后面跟着node1和node2两个节点，目标是把node1和node2交换位置，变成cur -> node2 -> node1 -> ...。

第一眼看上去只需要三步：

1. cur.next = node2
2. node2.next = node1
3. node1.next = node2.next ?——等一下，问题来了。

第三步的时候，node2.next已经被改了吗？没有，如果你严格按照上面三步顺序执行，执行完第2步后，node2.next其实还是指向node1的（因为第2步只把node2.next设为node1，它原本指向的是node3）。不对不对，这里有个致命顺序问题。

我把我实测通过的代码写出来，你先看这个版本：

cpp复制ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = dummy;

    while (cur->next != nullptr && cur->next->next != nullptr) {
        ListNode* node1 = cur->next;          // 保存第一个节点
        ListNode* node2 = cur->next->next;    // 保存第二个节点

        node1->next = node2->next;  // 第一步：node1 指向 node3（先留好后路）
        node2->next = node1;        // 第二步：node2 指向 node1（完成交换）
        cur->next = node2;          // 第三步：前驱指向新头 node2

        cur = node1;                // 后移两位，进入下一轮
    }

    return dummy->next;
}

这里的关键区别在于：第一步先让node1->next跳到node2->next，把后面的链条留住，然后再让node2->next指回node1。如果顺序反了，先执行node2->next = node1，那后面node3开头的整条子链就跟你彻底失去联系了——node2->next原本指向node3，被改成node1后，node3再也找不到了。

我当年第一次做这道题，犯的错就是这个顺序问题。提交后报错，我用纸笔画了半天才意识到：交换两个节点其实不是"两个节点之间的事"，而是三个指针的配合——前驱、当前交换的第一个节点、第二个节点。记住一个口诀："先连后面，再接前面，最后更新前驱。"具体说来：

• 先让node1指向交换后的后继（也就是node2原来的后继）；
• 再让node2指向node1；
• 最后让前驱cur指向node2。

为什么要按这个顺序？本质上是要保证每一步之后，不存在任何"整个链表从某个节点断开"的时刻。操作链表指针和用筷子夹菜是一个道理——你得先夹住新的，才能松掉旧的，不然菜就掉桌上了。这种思维模式一旦建立起来，后面刷反转链表、翻转区间这些题目，你就不会再被"指针指向哪里"这个问题搞晕了。

还有一个细节容易被忽略：循环的终止条件。这道题里我写的是cur->next != nullptr && cur->next->next != nullptr，意思是当前处理节点的后面至少还有两个节点可以交换。如果只剩一个节点或者没有节点，就停止。很多人会写成cur->next != nullptr，结果是每轮只处理一个节点，逻辑直接错乱。这两个条件出现的顺序也有讲究——C++的&&是短路求值，所以应该先检查cur->next是否为空，如果为空就直接返回，根本不会去访问cur->next->next，避免了空指针访问。

3. 双指针在链表里的两个派系：先走N步和追逐相遇

Day4这四道题里有三道都可以用双指针解决，但它们的"指针策略"完全不同。我建议你把它们分开理解，不然做题时会混。

3.1 间隔固定步数的双指针：删除倒数第N个节点

19题删除倒数第N个节点，题面要求一次遍历完成。如果你只是第一次做这道题，可能会想：先遍历一遍得到链表长度L，那倒数第N个就是正数第L-N+1个，再来一次遍历就行了。这个解法完全正确——但笨，足足做了两次遍历。

双指针的玩法是：搞两个指针fast和slow，先让fast往前走n步，然后两个指针一起往前走。当fast走到链表末尾（指向nullptr）时，slow刚好停在待删除节点的前一个位置。这时让slow->next = slow->next->next，删除就完成了。

这个思路的本质是制造一个长度为n的"滑动窗口"。窗口的前沿是fast，后沿是slow，当窗口前端抵到边界时，后沿自然就位了。这里最需要注意的是步数计算：到底让fast先走n步还是n+1步？

我实测后告诉你答案：走n步，然后fast和slow一起走到fast为空，此时slow指向倒数第n+1个节点（也就是待删节点的前驱）。举个例子，链长5，n=2，要删倒数第2个（节点4）。先让fast走2步到节点3，然后sllow从虚拟头开始同步走：fast到节点4时slow到节点1，fast到节点5时slow到节点2，fast到nullptr时slow到节点3——节点3正是节点4的前驱，完美。但如果让fast走n+1=3步再同步走，你会发现fast到nullptr时slow落在节点2，离待删节点隔了一个身位，删除逻辑就得改写。

为什么要用虚拟头节点？因为如果链表只有1个节点，删除倒数第1个节点，也就是删掉唯一的节点，删除后链表为空。如果没有虚拟头节点，slow初始指向head，fast走一步后已经是nullptr，同步走时循环一次都不执行，slow还是指向head——你根本没有办法把head删除。有了虚拟头节点，slow初始在dummy上，走n步后的同步过程中slow最后停在dummy（因为循环不执行），此时dummy->next = dummy->next->next，头节点被成功删除，而且你只需要返回dummy->next就能拿到空指针，逻辑完全统一。

3.2 快慢不同速的双指针：环形链表II的数学推演

142题环形链表II，要求找到入环的那个节点。这道题有两个关键问题：第一，怎么判断链表有环？第二，怎么找入环点？

判断有环的思路大家可能都听过：两个指针，fast每次走两步，slow每次走一步，如果链表有环，它们迟早会相遇；如果没环，fast会先碰到nullptr退出循环。这个"套圈"的例子在生活中很常见——学校操场跑步，你跑得快、你同学跑得慢，只要跑够时间，快的人一定能从后面追上慢的人。

但真正有意思的是第二个问题的推导过程，这才是这道题的灵魂。假设从头节点到入环点的距离为D，入环点到相遇点的距离为S，环的长度为L。那么当slow到达入环点时，它走了D步；与此同时fast已经在环里转了k圈又走了S步。如果让两个指针在环中继续走，fast的步速是slow的两倍，它和slow相遇前，fast一定比slow多走了至少一圈的路程。

简单说结论（这部分推导是经典的快慢指针结论，证明过程在LeetCode官方题解里有非常详细的版本）：当fast和slow第一次相遇时，新开一个指针index1指向相遇点，index2指向头节点，让index1和index2以相同速度往前走，它们相遇的位置就是入环点。

我第一次看到这个结论时觉得难以置信，但实际证明后会发现它非常优雅。原因在于相遇时，fast走的总路程是slow的两倍，而它们都在环里抵消掉了相同的圈数，最后会推出一个关键等式：从头节点到入环点的距离，等于从相遇点继续走到入环点的距离。也就是说，你从相遇点出发走一段路，和从头节点出发走一段路，会在同一个地方碰头——那个地方就是环的入口。

这道题能带给你的不仅是"会用双指针"，更是让你体会到一个算法工程师的日常：光写出能跑的代码不够，能证明它为什�对，才算真正掌握。面试中面试官特别喜欢针对这道题追问细节，比如"你能证明相遇时快指针一定比慢指针多走一圈吗""为什么相遇点走到入环点的距离恰好等于头节点到入环点的距离"。你要是能当场画图推一遍，基本就是加分项。

3.3 对齐起点的双指针：链表中点与链表相交的判断

面试题02.07链表相交这道题，其实是双指针思想的一个变种：先让两条链表"对齐"，再从同一个起点出发沿途比较。

具体做法是把两条链表分别遍历一遍，得到各自的长度，然后算出长度差。让较长那条链表的指针先走完这个差值，这样一来，两个指针就站在了"距离各自链表末尾同样远"的位置。接着两个指针同步移动，一旦遇到相同节点，那就是第一个交点。

这里有个很容易踩的认知偏差：两个链表相交，不是值相等就完事，而是节点地址（引用）相同。在C++里就是node1 == node2指针相等，在Python里就是id(a) == id(b)或a is b，而不是比较node.val是否相等。我见过有人拿值相等来判断，结果在链表恰好有两个连续节点值相同的地方误判了。这个错误在LeetCode上会直接报错，因为测试用例里专门设计了这种干扰项。

为什么双指针对齐的思路有效？因为两条链表如果相交，那么从交点开始，后面所有的节点都是共享的，也就是"尾部对齐"。如果两条链表的长度不一致，直接同步走的话，短链表的指针会先走到交点区域，而长链表还没到。先把长链的指针往前拉一段，让两边剩余路程一样长，那么它们必然同时走到交点。这个"尾部对齐"的思路在你后面做合并两个有序链表、求两个数组交集之类的题目时，也能迁移使用。

4. 链表题的临界状态全集：while循环和空指针是最大的"隐藏考官"

刷完day4这四道题，我很确定地告诉你一个规律：大多数链表题的bug，不是逻辑完全错了，而是临界状态的边界条件没写对。链表这个数据结构长得简单，它的"临界状态"却特别多，我干脆把它们整理成一张对照表，这张表是我刷了上百道链表题之后的个人经验总结，希望对你有用：

这张表里的每一个场景，我都在LeetCode上以外的代码里犯过不止一次。尤其是"先连前驱"这个错误，交换节点那道题但凡没有在纸上画图，几乎必错。

还有一个特别容易被忽视的点：while循环的终止条件到底是什么。在删除倒数第N个节点里，终止条件是fast != nullptr，为什么不是fast->next != nullptr？因为fast->next == nullptr意味着fast已经指向了最后一个节点，不是"越界"状态，此时slow停在倒数第N+1个节点，删除操作还没执行——你提前终止了。而fast == nullptr意味着已经完全走完链表，slow正好停在倒数第N+1个位置，这时候执行删除刚刚好。这个微妙的差别，直接决定你代码对还是错。

处理链表临界状态的心法，我认为可以浓缩成一句话：每次写循环之前，问问自己"终止时所有指针分别停在哪里"，然后画图验证。画图不丢人，一个在纸上画图花了两分钟的人，比那个直接敲代码半小时调不出来的高手，效率高得多。

5. 本地验证链表的"土办法"：构造用例和Print大法的正确姿势

很多刷题的朋友只用LeetCode自带的判题系统，做完就扔，从不做本地验证。这其实是个很大的短板。因为LeetCode会直接告诉你哪个case错了，你不用自己构造测试数据，推理能力得不到锻炼。而真实工作中写链表相关代码，根本没有一个"在线判题师"帮你看对错。

我个人的习惯是，每刷完一道链表题，都会在本地建一个main函数，把三个工具函数写好：createList（根据数组构造链表）、printList（打印整个链表）、deleteList（释放内存）。这三个函数加起来不超过三十行，却是链表调试的黄金搭档。

cpp复制// 根据数组构造链表
ListNode* createList(vector<int>& nums) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur != nullptr) {
        cout << cur->val;
        if (cur->next != nullptr) cout << " -> ";
        cur = cur->next;
    }
    cout << endl;
}

为什么打印代码这么重要？因为链表问题如果出错，只盯着代码看很难发现问题，尤其是涉及断链时。但一旦你打印出链表当前的值序列，对比预期结果，就能迅速定位是哪一段逻辑出错。比如两两交换那道题，如果输出是2 -> 1 -> 3 -> 4，说明第一轮没问题；如果是2 -> 1 -> NULL，说明后面的链条在你交换第一对时就断了——这时候你就知道应该检查"断链前保存node2->next"这一行。

我在本地调试链表时还发现一个技巧：给关键步骤后加临时打印，而不是一次性把所有打印写满。比如删除倒数第N个节点那道题，我会在fast走完n步之后打印一下fast->val，确认前进的步数对不对；再在同步移动的每一轮打印两个指针的位置。这样每一步的输入输出都可视化，调试效率至少提升一半。

这个方法在LeetCode上没法直接做，因为main函数不可见。所以我的建议是：每道题AC之后，把代码粘到本地，先跑一遍自己随机生成的测试数据，再跑几个边界case——空链表、单节点、双节点、头尾删除、环入口在中间等。别怕麻烦，这些边界case测试过之后，你对这道题的理解深度会完全不一样，下次遇到换皮的变种也不会慌。

6. 从Day4到所有链表题：一套可复用的"三步拆解方法论"

Day4的四道题刷完之后，我建议你停下来做个归纳，不要急着往下刷。因为链表题虽然数量多，但解法套路高度集中，我把它们总结为三步方法论，后续遇到任何链表相关题目都可以套用：

第一步，判断需不需要虚拟头节点。只要涉及头节点的删除、交换、修改，优先考虑dummy。判断标准很简单：如果头节点可能被改掉或者被删掉，那就需要。不需要的标准是：如果题目只是纯粹的遍历、查找、统计，那直接操作就行。

第二步，判断需不需要双指针。链表题里的双指针主要有三种形态：快慢指针（判断环、找中点）、间隔指针（找倒数第N个）、对齐指针（找相交点）。一旦题目出现"一次遍历""原地修改"这种关键词，基本就是在暗示你用双指针。

第三步，画图验证临界状态。写代码之前，先把链表画出来，从空链表、单节点、双节点、长链四类情况各画一遍，把每个指针在初始状态、中间状态、结束状态的指向都标清楚。这一步看着笨，实则是所有链表高手的日常习惯。面试的时候，面试官看你画图，不会觉得你菜，反而觉得你思路清晰。

另外，我特别建议你练一下"三指针模板"：pre、cur、temp。在很多链表操作里，这三个指针是标配。pre记录前驱，cur记录当前节点，temp用来在修改指针前保存下一个节点。day4的两两交换节点，本质就是多次执行这个三指针模板。反转链表、反转区间、删除节点、甚至更复杂的排序链表，底层也都是这套思路。

还有一点想单独提醒：如果以后刷题遇到"合并两个有序链表""反转链表的前N个节点""K个一组翻转链表"，你会发现它们的核心逻辑和day4这批题高度相似。原因很简单，链条操作如果不改变节点值，只在节点层面调整指针方向，那么能做的操作其实就那几类：断开、连接、翻转、移位。你只要把这几种基本操作练成肌肉记忆，就不存在"不会做"的链表题，只有"不熟悉场景"的链表题。

我现在的刷题习惯是：每做完一道链表题，不管AC没AC，都会在草稿纸上画一张三行的表——第一行写输入的链表结构，第二行写操作步骤（每一步改变哪个指针），第三行写出错的可能位置。看起来有点费时间，但这是把"知其然"升级到"知其所以然"的最快路径。

最后说个我自己学到的小经验：刷链表题的时候，别拿眼睛"跑代码"。人的肉眼无法跟踪三个指针的动态变化，但纸笔可以。拿到题目之后先画十分钟图，一笔一笔把指针挪动的过程画清楚，再开始敲代码，你对这道题的理解会深刻得多。这位"笨办法"陪我把day4的四道题全部拿下，也陪我在大大小小的面试里稳定发挥。希望你也能从这篇笔记里，找到属于自己的链表解题节奏。