企业官网建设流程全解析

四道链表题，一个共同套路：虚拟头节点与双指针思维

先说说这四道题的共同点。为什么训练营要把它们安排在同一天？因为它们本质上都在反复训练链表题的两个核心武器：虚拟头节点（dummy node）和双指针。你把这套组合拳打熟练，链表题基本就通了一半。

适合谁看？正在刷链表题但总觉得“代码能跑但思路不清晰”的同学，或者面试前想快速梳理链表题型的人。我尽量把每道题的思考路径、易错点、边界情况都讲透，你跟着走一遍，比闷头刷十道题都强。

1. 整体设计与思路拆解：先建立链表题的操作系统

1.1 虚拟头节点的本质：统一边界操作

链表题最烦的是什么？不是逻辑难，而是边界情况多。头节点被删了怎么办？链表为空怎么办？只有两个节点怎么办？每次都要写if判断，写多了就乱。

虚拟头节点的出现就是为了解决这个问题。做法很简单：在真正的头节点之前，先挂一个dummy节点，它的next指向真正的头节点。这样一来，头节点变成了“普通节点”，你对头节点的操作和其他节点完全一样，不需要单独写特殊逻辑。

这个思路跟操作系统里的“虚拟内存”有点像——用一个抽象层把复杂的物理细节统一掉，上层只管用统一的接口操作。链表里的dummy节点就是这个抽象层：让“删除头节点”和“删除中间节点”变成同一种操作。

提示：dummy节点不要命名为head，否则代码读起来会混淆。习惯上叫dummyHead或dummy即可，它本身的值（val）不重要，永远不用。

1.2 双指针：链表题的半壁江山

这一天四道题里，有三道（删除倒数第N个、链表相交、环形链表）直接用了双指针，剩下一道（两两交换）虽然名字不叫双指针，但本质也是三个指针在配合操作。可见双指针在链表里的地位。

双指针在链表里的应用主要分两种模型：

第一种，快慢指针。一个走两步，一个走一步，利用速度差制造“里程差”，用来找中点、判环、找倒数第N个节点。删除倒数第N个和环形链表都用的这个模型。

第二种，同速错位指针。两个指针速度一样，但起点不一样，制造“位置差”。链表相交是对齐两个链表长度后同时走，本质就是消除起点差。环形链表找入环点时，一个指针从头走，一个从相遇点走，也是同速起点差。

在学习的时候，把题目抽象成模型，比单独背某道题的解法有用得多。因为面试官不会考原题，但会考模型。

1.3 画图大于看代码：一个必须养成的习惯

说个实在话：链表题如果只盯着代码看，永远学不明白。我见过太多同学刷链表题的方式是“看题 -> 看答案 -> 背代码”，结果换一道就懵。链表这东西，本质上是一堆节点在“串珠”，你脑中必须有动态的画面感。

我的习惯是：拿到题目先在纸上画出链表的形态，用一个方框代表节点，用箭头代表next指针，然后手动模拟几步操作，再把指针移动的顺序写下来，最后才写代码。这一步看着浪费时间，实际是最省时间的。你手动模拟一遍走了几个分支，边界情况在图纸上一目了然。

后面每道题我都会先讲“图纸上的过程”，再给代码，就是为了帮你建立这种画面感。

2. 两两交换链表中的节点：指针顺序比你的记忆力更可靠

2.1 题目拆解与易错点

题目要求：给定链表 1->2->3->4，两两交换相邻节点，变成 2->1->4->3。注意是交换节点本身，不是交换节点的值。这俩的区别在于：交换值不改结构，实现简单但面试官通常不接受；交换节点要重新接线，考验对指针的理解。

这道题的易错点有三个：

第一个，交换之后，前一个交换块和后一个交换块怎么接上？很多人只盯着交换的那两个节点，忘了前面还有一组，结果链子在中间断开了。

第二个，循环条件怎么控制？while循环的终止条件写错，要么少处理一截，要么访问空指针。这个必须结合链表长度的奇偶来讨论。

第三个，交换完成后，cur指针该挪到哪？如果挪错了，下一轮交换的节点可能会被跳过一个。

2.2 迭代实现与指针顺序详解

先别急着看代码，我们走一遍图纸。假设链表是 dummy -> 1 -> 2 -> 3 -> 4，cur指向dummy。

第一步，我们要交换1和2。我们需要三个指针：cur（指向1的前驱）、node1（指向1）、node2（指向2）。交换后，链表应该变成 dummy -> 2 -> 1 -> 3 -> 4。

关键操作顺序：

1. cur的next指向node2（2），此时dummy连向2。
2. node1的next指向node2的next（3），此时1连向3。
3. node2的next指向node1（1），此时2连向1。

三步之后，链表变成了 dummy -> 2 -> 1 -> 3 -> 4，完美。

然后cur怎么走？注意，下一轮要交换的是3和4，而3的前驱是1，所以cur应该移动到node1的位置（也就是交换后处于第二位的那个节点）。写成代码就是 cur = cur->next->next，因为在当前状态下，cur->next是2，cur->next->next是1。

循环的终止条件是什么？如果链表剩下至少两个节点才继续。具体来说，就是 cur->next != nullptr && cur->next->next != nullptr。前者对应链表长度为偶数时，最后一组交换完，cur移动到第二个节点位置，此时cur->next可能为空；后者对应链表长度为奇数时，最后一组交换完，后面只剩一个节点，无法两两交换。

完整代码：

ListNode* swapPairs(ListNode* head) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; while (cur->next != nullptr && cur->next->next != nullptr) { ListNode* node1 = cur->next; ListNode* node2 = cur->next->next; // 三步换向 cur->next = node2; node1->next = node2->next; node2->next = node1; // cur前进到下一组的前驱位置 cur = node1; } ListNode* result = dummyHead->next; delete dummyHead; return result; }

注意：一定要先保存node1和node2的地址，再开始改指向。因为当你执行cur->next = node2之后，原来的node1就“悬空”了——通过cur->next已经拿不到它了。写代码前把这一步想明白，就不会出现“明明逻辑没错但链表断开”的情况。

2.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; }

这段代码很短，每次递归处理一对节点，返回处理后的新头节点。我个人的建议是：递归解法看看就行，面试时首选迭代。不是因为递归不好，而是链表题在面试里往往要求你写清楚指针的移动过程，迭代版更容易向面试官展示你的思路。

如果你非要吃透递归，记住一个规则：递归函数返回的是“处理完这一对节点后，这一段的头节点”。这样一层层往上，整个链表就串起来了。

3. 删除链表倒数第N个节点：一次遍历的双指针解法

3.1 从暴力到双指针的思路演变

这道题的常规思路是：先遍历一遍链表算出总长度L，然后删除正数第L-N+1个节点。这个思路没有任何问题，面试时可以先提出来作为baseline，但面试官紧接着会问：“能不能只遍历一次？”

这就引出了双指针解法。

想象有两个指针，一个叫fast，一个叫slow。fast先出发，向前走n步。此时fast和slow之间相距n个节点。然后fast和slow每次都走一步，保持这个距离。当fast走到链表末尾（遇到nullptr）时，slow刚好在倒数第n+1个节点，也就是待删除节点的前驱位置。

这跟生活中的排队思维很像：两个人同时开始走，一个人提前n步出发，当前面的人到达终点时，后面的人自然距离终点n步。你不用“数”总共有多少人，只需要利用距离差。

为了统一删除头节点的情况，这里同样使用虚拟头节点。让slow从dummy出发，当fast走到nullptr时，slow指向的正好是待删除节点的前驱。

3.2 代码实现与边界分析

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* fast = dummyHead; ListNode* slow = dummyHead; // fast先走n步 while (n-- && fast != nullptr) { fast = fast->next; } // 这里因为题目保证n有效，所以不需要再判断fast是否为nullptr // 同步前进 while (fast->next != nullptr) { fast = fast->next; slow = slow->next; } // 此时slow指向待删除节点的前驱 ListNode* toDelete = slow->next; slow->next = slow->next->next; delete toDelete; ListNode* result = dummyHead->next; delete dummyHead; return result; }

边界情况分析：

当n等于链表长度时，fast会走到nullptr之后，此时slow还在dummy位置，slow->next就是原来的头节点，删除后结果为空链表，代码逻辑完全正确。

当链表只有一个节点且n等于1时，fast先走一步到nullptr，同步循环不执行，slow->next就是头节点，直接删除，结果为nullptr，正确。

我把这个解法吃过之后，顺便说一下很多同学会踩的一个坑：第二个while的终止条件是fast->next != nullptr而不是fast != nullptr。为什么要多绕一层？因为当fast停在最后一个节点时，slow恰好指向待删除节点的前驱。如果条件写成fast != nullptr，fast会多走一步变成nullptr，而slow会走到待删除节点本身的位置，那就很难删了——你找不到它的前驱了。这也是为什么链表删除题一定要记住：单链表只有next指针，你必须站在前驱的视角去删除。

3.3 变体：双指针模型的泛化

其实这道题的双指针思想可以迁移到很多场景：找链表中间节点（快指针走两步，慢指针走一步）、判断链表是否有环（快慢指针速度差）、找两个链表的交点（对齐长度后同步走）。模型都是一样的，无非是把“距离差”用不同的方式制造出来。

我特别喜欢把它当作“双指针技术的三件套”来记：制造距离差 -> 保持距离差 -> 利用距离差。删除倒数第N个是先生成距离差，然后保持距离差走到底；链表相交是先把长链表的指针多走几步消除距离差，然后同步走。

4. 链表相交：两种方法，一个核心

4.1 题目本质：这题不难，但很多人想歪了

题目给定两个链表，需要找到它们相交的起始节点。很多同学第一反应是“比较节点的值”，这是大坑。相交的定义是“两个链表在某个节点开始，后面的节点完全共用”，所以比较的应该是指针（地址），而不是值。两个不同位置的节点完全可以有相同的值，但它们不算相交。

题目要求的返回值是节点本身（而且题目通常要求不能修改原链表）。

这里有个隐藏条件值得注意：两个链表相交后，因为单向链表只有一个next指针，所以相交后的所有节点都是一样的。也就是说，两个链表的结构是“Y”字形，而不是“X”字形。

理解这一点很重要，它直接引出了下面两种解法。

4.2 解法一：先求长度，再对齐末尾

最直观的做法：分别遍历两个链表，求出各自的长度。然后让长链表的指针先走差值步，让两个指针“站在同一起跑线”，再同步向前走，每走一步比较指针是否相等。第一个相等的节点就是交点，如果走到nullptr都没有相等，说明不相交。

[\text{lengthA} - \text{lengthB} \quad (\text{假设A更长})]

代码长这样：

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int lenA = getLength(headA); int lenB = getLength(headB); ListNode* pA = headA; ListNode* pB = headB; // 让pA指向更长的链表 if (lenA < lenB) { swap(pA, pB); swap(lenA, lenB); } // 长链表先走差值步 int gap = lenA - lenB; while (gap--) { pA = pA->next; } // 同步走并比较 while (pA != nullptr) { if (pA == pB) return pA; pA = pA->next; pB = pB->next; } return nullptr; } int getLength(ListNode* head) { int len = 0; while (head != nullptr) { len++; head = head->next; } return len; }

这个解法的核心思想是：既然两个链表从交点开始就共享一条路径，那么把两个指针挪到距离尾部相同的位置，然后同步走，它们一定会在交点相遇。如果快速判断两个链表的“后半段”是否重叠，只需要看尾部节点是否相同。

4.3 解法二：双指针互相走完对方的链表（优雅但需要理解）

这个解法我第一次看的时候，觉得太巧妙了。两个指针pA和pB分别从headA和headB出发，每次走一步。当pA走到末尾时，让它跳到headB继续走；当pB走到末尾时，让它跳到headA继续走。这样两个指针都走了“链表A的长度 + 链表B的长度”这么多步，会在交点相遇（如果存在的话），否则会同时走到nullptr。

用公式解释一下：假设链表A的长度为a，链表B的长度为b，它们的公共部分长度为c。那么pA走过的路径总长度是 a + (b - c)（先走完A，再走B中不属于公共部分的部分），pB走过的路径总长度是 b + (a - c)。化简后发现两者相等，都是 a + b - c。所以它们最终会在交点的起始处相遇。

代码非常简洁：

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA = headA; ListNode* pB = headB; while (pA != pB) { pA = pA ? pA->next : headB; pB = pB ? pB->next : headA; } return pA; // 不相交时返回nullptr，因为两个指针同时到达尾部 }

这段代码看起来有点“魔幻”，但手动模拟几次就通了。我第一次用这段代码时犯了错——在pA为空时直接跳headB，而不是先走完再跳，导致死循环。正确的写法是：每次只走一步，走到nullptr时下一次循环才跳转。这串代码里 pA = pA ? pA->next : headB 恰好实现了这个逻辑。

两种解法选哪个？我在训练营里看到很多同学推荐第二种，因为它省去了先求长度的步骤。但我的建议是：面试时先说第一种，因为它更容易讲清楚，面试官也更容易理解。说完之后可以补一句“如果要求代码更简洁，还可以用互相交替走的方式”，展示你对这个问题的深入理解。先把稳的答出来，再把漂亮的亮出来，这是面试的节奏。

5. 环形链表II：判断环与寻找入环点的完整推导

5.1 题目含义与两问拆分

这道题包含两个问题：第一，链表里有没有环？第二，如果有环，环的入口在哪里？很多同学在LeetCode上分别做过“环形链表”（只判断有没有环）和“环形链表II”（找入口），但第一次做这一版时没有把两个问题拆开思考，导致过程混乱。

判断有没有环，用快慢指针即可：快指针每次走两步，慢指针每次走一步。如果链表无环，快指针会先到达nullptr；如果有环，快指针会在环里不断打转，最终和慢指针相遇。注意：是“相遇”说明有环，而不是“快指针超过慢指针”。为什么用两步而不是三步？因为两步保证快慢指针的“相对速度”是1步，慢指针不会跳过快指针；速度差太大可能出现永不相遇的情况。

找到相遇点之后，第二个问题来袭：怎么找环的入口？

看到这里，你可以停下来想一下。如果只告诉你“快慢指针在环里的某点相遇了”，你第一步会做什么？

很多方案是从相遇点出发，继续走并计步，绕环一圈就能得到环的长度k，然后重新用两个指针，一个从head出发，一个从head前偏k步出发，理论上也能找入口。但代码写起来略繁琐。

实际上，这道题有一个非常优雅的数学结论，我第一次推完被震撼到了：从相遇点到环入口的距离，恰好等于从头节点到环入口的距离（在不考虑环的长度的情况下）。这直接导出一个简单解法：把快指针（或慢指针）重新放到head，两个指针都改成每次走一步，继续走，它们必定在环入口相遇。

5.2 数学推导：为什么两个同速指针必然在入环点相遇

设链表头到环入口的节点数为a，环入口到快慢指针第一次相遇点的节点数为b，环的总长度为L（从入口开始绕一圈回到入口的节点数）。

快指针速度是慢指针的两倍。当两指针第一次相遇时，慢指针走了 (a + b) 步，快指针走了 (a + b + nL) 步（其中 (n) 是快指针在环里多绕的圈数，至少为1）。

因为快指针的速度是慢指针的两倍，所以： [ 2(a + b) = a + b + nL ] [ a + b = nL ] [ a = nL - b ]

看右边这个式子：(nL) 是环长度的倍数，减去 (b) 之后，剩下的步数正好是从相遇点继续走到环入口的“剩余步数”（因为相遇点到入口的距离就是 (L-b) 加上若干圈）。如果 (n=1)，(a = L-b)；如果 (n\geq 1)，同样成立，因为绕了n圈最终都要回到入口。

所以结论非常干净：从头节点走到入环点的步数，等于从相遇点继续走到入环点的步数（可能多绕了几圈，但关键结论不变）。于是，只要把慢指针放回head，两个指针都每次走一步，它们一定会同时在入环点相遇。

这个结论第一次看可能有点绕，但你可以用纸笔画一个小环，手动模拟一下：比如链表头到入口有3个节点，环长4个节点。让快慢指针走一遍，找到相遇点，再放回头节点走一遍，你不仅会发现它们确实在入口相遇，还会彻底明白刚才的推导。画图永远是最好的老师。

5.3 完整代码实现

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) { // 有环，且相遇 break; } } // 如果没有环，fast走到nullptr if (fast == nullptr || fast->next == nullptr) { return nullptr; } // 第二步：两个指针重新从头和相遇点出发，同速前进 ListNode* p1 = head; ListNode* p2 = slow; // 即相遇点 while (p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; }

这段代码有几点需要强调：

第一，while循环的条件是fast != nullptr && fast->next != nullptr。因为快指针走两步，如果它在某个节点之后没有下一个节点了，说明链表没有环。这个条件也天然处理了空链表和单节点链表的情况。

第二，跳出循环后判断fast == nullptr || fast->next == nullptr。这是因为刚才的while有两种出口：一是遇到环内相遇，break出来；二是快指针触底，循环条件不满足，正常退出。后者说明没有环，返回nullptr即可。

第三，p1和p2相遇时，就是环的入口节点。这一步的数学依据就是上面的推导，写代码的时候心里要有底，不能“感觉应该是这样”就算完。

如果面试时想用更稳妥的“哈希集合”解法，也可以：遍历每个节点，用哈希集合记录地址，如果遇到已经在集合里的节点，那它就是环的入口。这个解法思路简单，空间复杂度O(n)。面试时如果先问“能不能用额外空间”，说明对方期待的是双指针的O(1)解法；如果能接受额外空间，哈希法是最好讲的备选。

6. 常见问题与排查技巧实录

6.1 高频报错与排查速查表

我把训练营里这几天常见的问题和解决办法整理成了表格，对照自查即可：

6.2 边界测试清单：每次交代码前检查一遍

链表题能不能过，边界情况占了八成功劳。每道题写完代码，我都会用下面这份清单自测一遍：

• 空链表（head == nullptr）
• 只有一个节点
• 只有两个节点
• 删除倒数第1个节点（即尾节点）
• 删除倒数第n个节点，其中n等于链表长度（即头节点）
• 链表长度恰好为偶数、奇数各测一遍
• 相交的两个链表长度相等 / 不相等
• 环形链表入口恰好是头节点
• 环形链表入口在链表尾部（入口的next指向头，即首尾相连的环）

比如两两交换，用空链表跑一遍看会不会崩，用奇数长度链表跑一遍看最后一个孤节点会不会被错误处理。删除倒数第N个，删头节点时务必验证删除后的链表是否完整。链表相交，两条链表的长度差恰好是0、1、大于1分别测试。环形链表，入口是头节点这种情况最容易漏。

6.3 训练营打卡的独家小技巧

分享几个我在训练营里学到的实用技巧。

第一个：写链表代码前，先在代码注释里写下指针移动的顺序。比如两两交换我总在代码最上面写上：

// cur -> node1 -> node2 -> nextNode // 交换后：cur -> node2 -> node1 -> nextNode

写注释的过程就是帮你想清楚的过程。等你把注释写清楚了，代码往往只需要几分钟。

第二个：遇到“删除节点”的题，一定要站在“前驱节点”的视角去想。单链表只能通过next指针访问下一个节点，所以删除谁，就得拿到谁的前驱。虚拟头节点的作用就是让头节点也有前驱。

第三个：在LeetCode或本地上跑调试时，自己写一个打印链表的函数。每次操作完打印一遍链表，用肉眼看看节点连接有没有断。这个习惯陪我解决了好多棘手的bug，比盯着代码看半小时效率高得多。

第四个：遇到数学推导（比如环形链表），不要害怕。先用具体数字（比如a=3, b=2）代入演算一遍，你会发现公式只是把具体规律抽象化了。推导通了，这个解法一辈子忘不掉。

到这一步回头再看这四道题，你可能会发现：两两交换练的是“指针重新穿线”，删除倒数第N个练的是“双指针制造距离差”，链表相交练的是“对齐起点”，环形链表练的是“快慢指针和数学规律的结合”。每一道刷完，都要问自己：这道题的核心模型是什么？哪里最容易出错？下次遇到类似题我能一眼识别吗？

我在实际做这四道题时花了比预期长得多的时间，尤其是环形链表的数学推导，第一遍没推明白，后来画了整整三页纸才算彻底通透。但从那以后，链表题的指针移动我再也没有犯过“写一步漏一步”的毛病。做题的意义不在于“AC那一刻的爽感”，而在于AC之前那段痛苦的思考——那才是真正长本事的地方。

如果你今天也卡在链表题上，不要急。先放下代码，拿出草稿纸，把链表的形状画出来，把指针的移动画出来，把边界情况画出来。画完你会发现自己离答案已经不远了。这四道题刷完，链表题的大门基本算是正式推开了，后面无论是反转链表、合并链表还是各种链表变体，你都会觉得“这题我见过”。