企业官网建设流程全解析

链表题在算法训练里一直是“看了解析觉得很简单，自己一写就卡住”的重灾区。评论区最常见的一句话就是：“我懂了，但是代码就是写不对。” 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-N+1个节点做删除。这个方法能过，但面试时会被追问“能不能只遍历一次”。

只遍历一次的核心难点在于：你不知道链表总长多少，但你又想定位倒数第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初始化为head，slow初始化为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指向dummy，slow->next指向head，执行slow->next = slow->next->next，返回dummy->next即为新的头。这个统一性正是虚拟头节点存在的意义。

3.4 极端用例的推演

• n等于链表长度：fast从dummy走n步后指向链表末尾的节点，此时fast->next是nullptr，直接跳过while循环，slow还在dummy，删除的是头节点。正确。
• 链表只有一个节点：fast走1步到NULL，slow在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的头继续走。这样一来，两个指针走过的总路程都是lenA+lenB。如果存在交点，它们会在交点处相遇；如果不存在，它们会同时走到nullptr。

我第一次看到这个解法时觉得像是魔术，后来想明白了：这本质上是把两个链表的长度差异“分摊”到两次遍历中，达到对齐效果。不过这个写法虽然简洁，面试时解释起来需要花时间。我的建议是先把长度差版本理解透，如果有余力再掌握这个进阶写法，两者各有适用场景。

5. 环形链表II：数学推导不只是为了证明，更是为了写对循环条件

5.1 快慢指针的相遇条件

环形链表II有两个子问题：第一，链表中存不存在环；第二，如果存在，找到环的入口节点。

判断有没有环，经典做法是快慢指针。快指针每次走两步，慢指针每次走一步。如果没有环，快指针会首先走到nullptr；如果有环，快慢指针最终会在环里相遇。

这里我有一个反复强调的细节：为什么快指针每次走两步而不是三步四步。走两步时，快指针相对于慢指针的速度差是1步，意味着每迭代一次，快指针离慢指针近一步，所以快慢指针必然会相遇。如果速度差大于1，虽然通常也能追上，但存在“跳过”慢指针的可能性（绕环多圈情况下），数学上更复杂，没必要给自己找麻烦。

5.2 入口推导过程

假设从链表头到环入口的距离为a，从环入口到快慢指针第一次相遇点的距离为b，从相遇点继续走到环入口的距离为c。环的总长度为b+c。

慢指针从头走到相遇点，走了a+b步；快指针走了a+b+k*(b+c)步，其中k是快指针比慢指针多绕的圈数。因为快指针速度是慢指针的两倍，所以：

2*(a+b) = a+b+k*(b+c) a+b = k*(b+c) a = k*(b+c) - b = (k-1)*(b+c) + c

当k=1时，a = c。这意味着：从链表头走到入口的距离，等于从相遇点继续走到入口的距离。当k>1时，从相遇点出发需要多绕几圈后再到入口，但“一个指针从头出发、另一个从相遇点出发，同速前进，最终会在入口相遇”这个结论依然成立。

有了这个推导，代码就非常直接了。

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)就是经典例子。
• 删节点后没有delete：C++里new出来的节点如果不手动释放会内存泄漏。刷题时不太要紧，但项目里这就是事故。

6.3 从这四道题出发可以继续刷什么

如果你把这四道题吃透了，我建议趁热打铁做几个延伸题，检验一下双指针思维的迁移能力：

• LeetCode 876 链表的中间节点：快指针走两步，慢指针走一步，快指针到末尾时slow就是中间点。
• LeetCode 61 旋转链表：先求长度，再把链表头尾相连，定位新头节点后断开。
• LeetCode 143 重排链表：找中点、反转后半段、再交替合并。这个题目几乎综合了链表操作里所有基本功。

这些题的核心操作，你都能在DAY4这四道题里找到影子。链表题的练习策略不该是“每道题背一遍模板”，而是“每种核心技巧练到条件反射”——看到链表题，先问自己要不要虚拟头节点，要不要双指针，两个指针之间是速度差还是间距差。想清楚这三个问题，题目就解了一大半。

7. 我刷完这四道题后的几点体会

这四道题在训练营里被安排在同一天，确实有它的道理。它们把链表的基本功拆得很细：两两交换练的是指针重连顺序，删除倒数第N练的是间距双指针，链表相交练的是对齐与同步，环形链表练的是快慢指针与数学推导。每道题单独看都不算难，但合在一起，几乎覆盖了所有链表指针操作的高频考点。

我自己刷的时候，最深的感触是：链表题不是靠脑袋想出来的，是靠图画出来的。两两交换那道题，我反复在纸上画了不下五遍才彻底搞明白指针重连的顺序；环形链表II那道题，我也是画了一遍推导图才真正理解为什么相遇点出发的指针能和头节点指针在入口相遇。

如果你现在觉得吃力，不要急。刷链表题就是这样，前面几道题卡顿很正常，量变到质变往往就在某几道题之后。VT虚拟头节点、双指针、先保存后继再改指针，这三个习惯一旦养起来，后面再做链表相关的复杂题，你会明显感觉自己变顺了。