链表核心技巧复盘：虚拟头节点、双指针与环形链表入口推导

代码随想录训练营day4，对于跟营的人来说，这天是链表章节真正上强度的一天。Day3还在处理单节点操作，Day4直接切换到多节点联动、长度对齐、环检测这些组合玩法。任务清单是四道题：24. 两两交换链表中的节点、19. 删除链表的倒数第N个节点、面试题02.07. 链表相交、142. 环形链表II。这四道题刷完，链表题最常用的几个套路基本就全覆盖了。

写这篇复盘的时候，我已经把这四道题在代码随想录的框架下完整过了一遍，同时用不同实现方式做了本地验证。整体感受是：今天的题目没有一道是“暴力硬解”能优雅收场的，每道题都在逼你理解指针的本质和边界条件。对于正在跟训练营的同学，这篇文章可以作为你刷完题之后的对照参考；对于准备面试、想集中突破链表题型的读者，这四道题的覆盖度也足够帮你建立起链表题的解题框架。

1. 训练营进入链表核心：今天这四道题到底在练什么

1.1 Day4在代码随想录路线里的位置

代码随想录训练营的刷题顺序不是随意排的，Day4放这四道题有它的逻辑。Day1和Day2解决的是数组问题，核心是连续内存上的双指针、滑动窗口、模拟行为。Day3进入链表，练了移除链表元素、设计链表、反转链表，本质上还是在处理“单个节点的增删改”。

到了Day4，题目突然从“单点”跳到“多点联动”。两两交换涉及到三个节点之间的三条指针变更，删除倒数第N个节点要用双指针控制距离，链表相交需要先对齐两个链表的尾部公共部分，环形链表II更是要判断环的位置。这种递进关系很清楚：先保证你能正确操作单个节点，再去处理节点之间的关系。很多人在Day3觉得链表简单，到了Day4就被指针绕晕，其实不是题目变难了，而是你还没建立“操作前先画图、拆步骤”的习惯。

我自己的感受是，Day4的核心并不是“会做这四道题”，而是借这四道题把链表的几个通用技巧内化成肌肉记忆：虚拟头节点、快慢指针、长度差对齐、数学推导找入口。这些技巧在后面二叉树、链表综合题里还会反复出现。

1.2 四道题共同指向的三层能力

把四道题放在一起看，可以发现它们考察的能力有明显的层次。

第一层是“在链表中安全地修改指针”。24题两两交换节点就是最典型的场景。这里没有任何花哨的算法，纯粹看你能不能把三四个指针按正确顺序接好，同时不丢失任何节点。很多新手写这类题最容易犯的错就是操作顺序不对，比如先把cur->next改了，结果后面要用到原cur->next时发现已经丢了。

第二层是“用双指针解决特定位置问题”。19题删除倒数第N个节点，表面上是定位问题，背地里是快慢指针保持固定距离的经典应用。链表相交则是先通过长度差对齐，再用双指针同步前进。这两种都属于“让两个指针在合适的位置相遇/同步”，是链表题里出现频率非常高的模型。

第三层是“用数学推理简化代码逻辑”。142环形链表II是最标准的例子。判断有没有环，快慢指针就能解决；但找入口就得靠推导x = z这一步。如果只记结论不推过程，面试时很容易被追问卡住。

这三层能力正好对应刷题时从“能写对”到“能讲清楚”的进阶过程。Day4安排的这组题，选得确实用心。

2. 让人又爱又恨的虚拟头节点：指针操作拆解

2.1 为什么链表题几乎离不开虚拟头节点

先解决一个基本问题：为什么这么多链表题都需要一个dummyHead？

因为在链表头部操作和中间操作不一样。比如删除头节点，如果你是直接对head操作，删除之后头节点变了，返回新头就很麻烦。更常见的是，你需要把当前节点固定在某个位置，然后统一用“cur->next->next”这种形式来操作目标节点的前驱，如果目标就是第一个节点，cur从head开始就会出现空指针问题。

虚拟头节点的核心价值在于：把对“第一个节点”的特殊处理，转换为对“普通节点”的统一处理。你在dummyHead这个位置设置一个cur，cur->next就是原链表的头节点。这样不管你要操作的是第几个节点，都能用同样的指针模式去写，边界条件少很多。

拿19题举例，如果不用虚拟头节点，删除倒数第N个节点且N等于链表长度时，要删的就是头节点。此时slow还停在dummy或者链表的某个位置，你的代码就得分情况讨论。用了虚拟头之后，slow最终一定指向待删除节点的前一个节点，head被删也只需要slow->next = slow->next->next，返回dummyHead->next即可。

虚拟头还有一个隐性好处：你的cur指针初始位置和链表长度无关。不管链表为空还是只有一个节点，dummyHead都存在，循环条件写成cur->next != nullptr也不会报空指针。这对统一逻辑非常有帮助。

2.2 两两交换节点：最容易丢指针的那道题

24题的要求是：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。不能单纯改变节点内部的值，需要实际进行节点交换。

看一眼示例：输入1->2->3->4，输出2->1->4->3。注意如果链表是奇数个节点，最后一个节点保持不动，比如1->2->3交换后是2->1->3。

这道题最大的难点在指针变更顺序。很多第一次做的人上来就写cur->next = cur->next->next，结果发现原来的cur->next（也就是第一个节点）找不到了。所以做这种题一定要先画图，把每条“线”都标出来再动手。

我的写法是先设置虚拟头节点，然后让cur指向dummyHead，循环条件为cur->next不为空且cur->next->next不为空。每轮交换涉及三个指针变更，我会先把需要用到的节点保存下来：

cpp复制class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        
        while (cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp1 = cur->next;              // 保存第一个节点
            ListNode* tmp2 = cur->next->next->next;  // 保存第三个节点
            
            cur->next = cur->next->next;  // 第一步：cur指向第二个节点
            cur->next->next = tmp1;       // 第二步：第二个节点指向第一个节点
            tmp1->next = tmp2;            // 第三步：第一个节点指向第三个节点
            
            cur = tmp1;  // cur移动到交换后的第二个节点（原第一个节点）
        }
        
        return dummyHead->next;
    }
};

这里最需要注意的是第一步完成之后，cur->next已经不是原来的第一个节点了。所以必须先把tmp1保存下来，否则走到第三步时你根本找不到原来的第一个节点。保存tmp2也是同理，因为第二步完成之后，新链表里可能就没人指向第三个节点了。

有同学会问：能不能不保存tmp2？可以，但你需要调整操作顺序，比如先把tmp1->next指向第三个节点，再处理cur->next和cur->next->next，这样tmp2其实可以临时访问到。不过我实战中发现，把三个节点都先存下来的写法最不容易出错，虽然多了两个变量，但逻辑清晰，调试起来也方便。

再提一个坑：更新cur的位置。很多人的代码在交换完之后忘了把cur移动到下一组的前驱位置，结果导致死循环或者无限交换。这里cur应该移动到tmp1，也就是当前这一组交换后的第二个节点，因为下一组的第一个节点是tmp1->next。

2.3 删除倒数第N个节点：虚拟头与双指针的合体

19题的要求是删除链表的倒数第N个节点，并返回头节点。要求一趟扫描完成，也就是说不能先遍历一遍算长度，再从头找位置。

一趟扫描怎么做？标准解法就是双指针，快指针先走N步，然后快慢一起走，快指针走到链表末尾时，慢指针正好停在待删除节点的前一个位置。这个思路本身不难，但有几个细节容易踩。

第一步，快慢指针都从dummyHead出发。这里用虚拟头不是为了统一头部删除，而是为了让slow最终落在待删除节点的前驱。如果从head出发，删除头节点时slow会落在head上，操作起来很别扭。

我的实现是：

cpp复制class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        
        // 快指针先走n步
        while (n-- && fast != nullptr) {
            fast = fast->next;
        }
        
        // 快指针再每次走一步，直到走到最后一个节点
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // 此时slow指向待删除节点的前驱
        slow->next = slow->next->next;
        
        return dummyHead->next;
    }
};

这里的关键是第二个循环的判断条件是fast->next != nullptr，而不是fast != nullptr。如果用后者，fast会走到nullptr，slow会走到待删除节点本身，而不是前驱，删除逻辑就要改成slow = slow->next再删，多一步不说，还要额外处理边界。

另外，快指针先走n步之后，如果n等于链表的长度，比如链表有3个节点，删除倒数第3个节点，那么fast先走3步会停在最后一个节点上。第二个循环不进入，slow还停在dummyHead，执行slow->next = slow->next->next，正好把头节点删掉。这个场景不用特殊处理，虚拟头的价值就在这里。

我在第一次写这道题的时候犯过一个低级错误：忘了判断fast是否为空，直接把fast->next拿来用。如果n传参等于链表长度且链表本身非空，这种情况其实不会触发空指针，但如果链表为空，fast从dummyHead走n步就会变成nullptr，这时候就只能看n的大小。所以稳妥一点，第二个循环前加一个fast != nullptr的判断比较好，虽然LeetCode的用例里n始终合法，但面试手写时显得更严谨。

3. 快慢指针的正确打开方式：相交与环形链表

3.1 链表相交：先对齐再找交点

面试题02.07.链表相交说的是：两个单链表的头节点headA和headB，找出并返回两个单链表相交的起始节点，如果两个链表没有交点，返回null。

这道题的坑点在于“相交”的定义。两个链表相交，从那个节点开始后面的所有节点都是同一个物理节点，也就是内存地址相同，而不是值相同。LeetCode这里判断的是指针地址相等，不是val相等。很多人写的时候用curA->val == curB->val来判断，提交直接挂掉。

解法思路其实不复杂：如果两个链表相交，那么从相交点开始到结尾的路程是一模一样的。所以我们可以先算出两个链表的长度，让长的链表指针先走长度差步，然后两个指针同步前进，遇到第一个地址相同的节点就是交点。

cpp复制class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        
        while (curA != nullptr) {
            lenA++;
            curA = curA->next;
        }
        while (curB != nullptr) {
            lenB++;
            curB = curB->next;
        }
        
        curA = headA;
        curB = headB;
        
        if (lenA < lenB) {
            swap(lenA, lenB);
            swap(curA, curB);
        }
        
        int diff = lenA - lenB;
        while (diff--) {
            curA = curA->next;
        }
        
        while (curA != nullptr) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

这里用swap处理长度差比较方便，确保curA一定指向长链表。我见过有些人不用swap，而是用if判断加两个while循环，那样代码会冗余很多。链表题里灵活用swap经常能让逻辑简洁不少。

除了这种方法，哈希集合也是一种可行方案：先把headA的所有节点存入unordered_set，再遍历headB，第一个出现在集合里的节点就是交点。这种方法时间复杂度同样是O(m + n)，但空间复杂度是O(m)，而双指针对齐法的空间复杂度是O(1)。LeetCode上还有一种更精妙的双指针交替走法，即两个指针分别从headA和headB出发，走到头之后切换到另一个链表头继续走，这样能自动消除长度差，两轮之内必然相遇或同时到nullptr。这个方法很优雅，但第一次理解稍微绕一点。训练营的打卡作业里用的是先计算长度差再对齐的版本，理解成本最低，也最不容易在面试现场写错。

3.2 环形链表II：从“有没有环”到“入口在哪”

142题要求：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，返回null。

环形链表I是只判断有没有环，快慢指针就够。但142要返回入口节点，这就涉及到数学推导了。

先回忆一下快慢指针判断环的逻辑：设置fast每次走两步，slow每次走一步，如果链表有环，两者必然在环内相遇，因为快指针相对慢指针每次多走一步，在环内一定能追上。

找到相遇点之后，入口怎么求？标准答案是：从链表头部出发的指针index1，和从相遇点出发的指针index2，每次都走一步，它们的第一次相遇点就是环入口。

这个结论不直观，必须推导一遍才能真的理解。设链表头到环入口的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z，环的总长度为y+z。

慢指针走的距离是x+y，快指针走的距离是x+y+n(y+z)，其中n表示快指针在相遇之前至少已经在环里走了n圈，n >= 1。因为快指针速度是慢指针的两倍：

2(x + y) = x + y + n(y + z)

化简得到：

x + y = n(y + z)
x = n(y + z) - y = (n - 1)(y + z) + z

当n = 1时，x = z。也就是说，从头部到环入口的距离，等于从相遇点继续走到环入口的距离。即使n > 1，式子变成x = (n-1)(y+z) + z，意味着index2在环里多绕若干整圈之后，与index1在环入口相遇。结论依然成立。

cpp复制class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                ListNode* index1 = head;
                ListNode* index2 = fast;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};

不要小看这个推导。面试的时候，你背下代码其实不难，但如果面试官问一句“为什么第二次相遇就是入口”，很多人会卡住。我建议备考的人认认真真自己在纸上推一遍上面的等式，把x、y、z的定义写清楚。推导熟练之后，这道题就不再是“背模板”，而是真正理解了。

还有一个小细节：判断有环时，循环条件fast != nullptr && fast->next != nullptr。有些链表题里会写成while (fast && fast->next)，一个意思。如果链表里没有环，fast会先走到nullptr或者fast->next为nullptr，自然退出。

3.3 快慢指针的边界条件汇总

Day4这两道快慢指针题，如果在面试时连起来考，其实是很经典的组合题。我把常见边界条件整理一下：

对于删除倒数第N个节点，需要确认n的取值范围。LeetCode保证n是有效的，也就是1 <= n <= 链表长度。但如果面试官出的题不保证有效，你就得在动指针之前先判断。我一般会先处理“链表为空”的情况，再处理n等于链表长度的情况，虽然虚拟头已经解决了后者，但写出这层判断会让面试官觉得你考虑问题全面。

对于环形链表，边界条件集中在“链表为空”“链表只有一个节点”“链表没有环”三种情况。fast从head出发，如果链表只有一个节点且没有环，第一次while判断fast->next == nullptr直接退出，返回nullptr。如果链表有两个节点且有环，slow和fast会在第二次循环时相遇，逻辑也能覆盖到。

我在刷题时习惯在纸上列出所有可能的链表形态：空链表、单节点链表、无环链表、尾节点指向头节点的环、尾节点指向中间某个节点的环。列完之后，再用代码一一验证，基本不会漏掉边界情况。

4. 实操复盘：从思路到AC的完整记录

4.1 本地调试链表题的方法

很多人刷LeetCode链表题有个痛点：本地IDE里写代码没法直接看到链表结构，调试只能靠println打日志，效率很低。我在Day4这天用了几个土办法，效果很好。

第一个办法是写一个打印链表函数。

cpp复制void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur != nullptr) {
        cout << cur->val << " -> ";
        cur = cur->next;
    }
    cout << "nullptr" << endl;
}

用法很简单，每执行几步操作就打印一次当前链表。比如两两交换那道题，我每完成一个步骤就打印一次，很快就能看出是哪一步把链表结构改坏了。

第二个办法是手动构造测试用例。链表题不像数组题可以快速构造大数组，我一般直接逐个new节点构造小链表。比如24题我构造了1->2->3->4和1->2->3两组用例，分别验证偶数和奇数场景。19题我会额外测n等于链表长度、n等于1这两个极端情况。

第三个办法是画图。在草稿纸上画出每次指针变更前后的指向关系，标上节点编号，然后和代码一步一步对照。这个方法看起来原始，但确实是最不容易出错的排查方式。很多人觉得链表题难，其实不是代码难写，而是脑中缺少“指针对应关系”的图像。

4.2 我在训练营day4踩过的坑

写下我实际踩过、且估计很多人也会踩的几个坑。

第一个坑是24题里更新cur的位置。我第一次写的时候，交换完一组节点之后习惯性地写了cur = cur->next->next，结果第2组交换时指针全乱了。原因是交换完成之后，cur->next已经是原来这组的第二个节点，而新的下一组第一个节点是从tmp1->next开始的。我当时没有画图，凭感觉写，白白debug了将近二十分钟。后来在草稿纸上标完节点名，马上就看出来了。

第二个坑是19题的快指针初始前进距离。我一开始用的是“快指针先走n步”版本，但第二个循环我写的是while (fast != nullptr)，结果slow最终停在待删除节点上，后面还得再手动让slow = slow->next，逻辑变得很绕。后来我把第二个循环改成while (fast->next != nullptr)，slow自然停在待删除节点的前驱，代码简洁很多。这个问题在上一节已经详细解释过。

第三个坑是142题里没有把快慢指针相遇的节点保存下来。我在找到相遇点之后直接复用slow指针作为index2，然后和index1一起走，结果因为后续还有fast指针联动的逻辑，导致代码混乱。正确的做法是新建index1和index2变量，让它们独立承担找入口的任务，不要复用原来的指针。变量职责分离，在这种多指针题里特别重要。

第四个坑是在链表相交题里用值相等判断交点。我第一版代码写的是if (curA->val == curB->val)，提交样例没过。后来仔细读题才发现要求的是地址相同。这个坑提醒我：链表相关题目里，相等这个概念一定要看清楚是值相等还是地址相等。

4.3 链表题的AC标准与复盘方式

训练营的打卡要求是提交AC截图，但我觉得“能过”只是第一步。我在过完一遍之后会做第二轮复盘，标准很简单：把代码删掉，重新在白板上写一遍，要求自己在十五分钟内把四道题全部写出来。如果哪道题卡住超过五分钟，说明之前的理解还有漏洞。

这个习惯是我跟训练营之后才养成的。Day4这几道题代码量都不大，但涉及的知识点密度高。第二次默写时，我在19题的双指针细节上又卡了一次，说明第一遍刷完的记忆并不牢固。训练营的进度很快，如果不做这种复写练习，后两天学二叉树时会明显吃力。

复盘时我还会记录一道题的不同解法。比如19题除了快慢指针，还可以用递归或者栈来做，但面试时最优解是双指针。链表相交也可以用哈希集合。多记几种解法有助于对同一模型的理解，面试时如果被追问“还能怎么做”，也能答得上来。

5. 链表刷题高频报错与训练营节奏建议

5.1 链表题易错点速查表

我把Day4四道题及链表专题常见的错误类型整理成一张速查表，方便刷题卡住时快速定位。

这张表的适用场景包括但不限于Day4这四道题。它同时也是做链表类题目一个通用的自查清单。以后遇到任何链表问题，从这六类原因里面找，大概率能命中。

5.2 给刚开始跟训练营的人三个建议

第一个建议是不要跳题。Day4这四道题看起来有些重复，都是链表操作，但每一道题的侧重点都不一样。两两交换练的是多指针变更顺序，删除倒数第N个节点练的是双指针距离控制，链表相交练的是长度对齐，环形链表练的是数学推导。如果图省事跳了某一道，后面的二叉树题目里用到类似技巧时，你可能会感到吃力。

第二个建议是当天写完当天复盘。训练营的节奏是每天都有新题，前一天的内容如果不及时消化，第二天就会像滚雪球一样越积越多。我Day4这天的实际做法是：上午刷第一遍，下午做第二遍默写，晚上睡觉前再看一遍错题记录。这个流程听起来重，但每道题的代码量并不大，半小时内能全部完成。

第三个建议是多看讨论区。LeetCode每道题的讨论区里有不少热评解法，很多代码非常精炼。比如24题有人用递归写，代码只有五行，虽然面试不一定要求，但看一眼能拓展思路。我自己在链表相交题里看到双指针交替走法之后，就对长度差对齐有了更深的理解，这是只看一种解法学不到的。

5.3 后续复习与扩展思路

Day4的知识点不会只出现一次。后面刷二叉树时，很多遍历和构建问题里会用到链表或引用传递的思路。代码随想录后面的链表综合题里，也会反复出现快慢指针和虚拟头节点。

如果学有余力，我建议额外看看24题的递归写法、19题的栈解法、142题的哈希集合判环法。特别是142题，用哈希集合记录访问过的节点地址，遇到第一个重复地址就是入口，代码非常直观，虽然空间复杂度不符合进阶要求，但作为理解题的辅助手段很有价值。

最后再分享一个我很受用的小技巧：做链表题时，把每个节点的“角色”起一个清晰的名字。tmp1、tmp2、index1、index2这种命名，比单纯用指针的next串联要直观得多。命名混乱是链表题代码难读的第一大原因，变量角色清晰之后，调试和讲解都会轻松很多。这是我刷完Day4之后最大的一个收获，强烈推荐你也试试。