企业官网建设流程全解析

LeetCode 第 24 题“两两交换链表中的节点”，我在面试题单里看到它的频率高得不像一个 Medium 难度题。表面上就是相邻两个节点换位置，但真正能在 10 分钟内把递归和迭代两种写法都写对的人，我面过不下几十个，占比确实不高。这道题的核心不是“你会不会交换”，而是你对链表的指针操作、边界条件、以及递归返回值的理解到不到位。今天把我自己的做题笔记、调试点和踩过的坑完整整理出来，给正在刷题的朋友一份可以直接照着练的参考。不管你是刚开始刷 LeetCode 的新手，还是准备面试想快速过链表专题的老手，这篇文章都能让你少走点弯路。

1. 题目到底在考什么：先别急着写代码

1.1 题目描述与输入输出约定

题目原文其实很短：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。注意，你不能只是单纯的改变节点内部的值，而是需要实际的节点交换。

这里有个隐藏的约束：“不能只改变节点内部的值”。有些读者第一次看会疑惑，直接交换 val 不行吗？对于这题，如果只是求结果，交换 val 在 OJ 上是能通过的，因为 OJ 只检查最终链表的值序列。但面试场景下，面试官想看的是你操作指针引用的能力，而不是偷懒换值。链表这个数据结构之所以存在，就是因为节点在内存中不是连续存储的，调整关系只需要改变指针，不需要移动数据本身。如果你上来就交换值，等于把链表的优势丢掉了，考察点也就没了。

输入输出约定方面，链表节点定义通常是：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };

函数签名是ListNode* swapPairs(ListNode* head)，返回的是新链表的头。这里注意一个细节：交换后原来的第二个节点变成了新链表的头，函数的返回值必须是 newHead，而不是原来的 head。很多人递归版本写不出来，就是卡在“返回值到底是谁”这个问题上。

边界条件也很明确：链表为空，或者只有一个节点，直接返回原链表即可。这两个条件很重要，因为交换至少需要两个节点，这也是递归版本里递归基的由来。

1.2 为什么不能用交换值来偷懒

先说结论：交换值在 LeetCode 上确实能 AC，但我不建议你这么做。原因有三层。

第一个原因是面试考察点错位。面试官设置链表题，想看到的是你对 next 指针的重新连接、对内存关系的理解，以及处理指针悬空的能力。你直接swap(head.val, head.next.val)，代码只有一行，完全体现不了这些能力。面试官会觉得你是在“绕过题目”，而不是“解决题目”，印象分会大打折扣。

第二个原因是工程里的真实场景不允许。实际业务中链表节点往往带有多个字段，比如一个订单节点里有订单号、金额、时间戳、关联指针等。交换值意味着复制整块数据，时间复杂度和空间复杂度都会上涨；而调整指针只是改动几个引用，开销是常数级别的。当节点包含一个很大的对象或者深拷贝字段时，交换值的代价可能比调整指针高一两个数量级。

第三个原因是刷题的目的就是锻炼操作指针和递归结构的能力。这道题最典型的价值就在于它要求你处理节点之间的引用关系，如果绕过这个，整道题对你没有任何训练意义。退一步讲，即使不考虑这些，面试的时候你写个 swap(val) 出来，也很难让面试官相信你真的理解链表。

1.3 两种主流解法的选型逻辑

这道题的标准解法就两大类：递归和迭代。递归版本思路简洁、代码短，适合理解“子问题”的概念；迭代版本用哑节点加循环，适合面试现场手写，不容易出错。

递归的思路是这样的：把链表看成一个递归结构，只要当前 head 和 head.next 都存在，就把这两个节点交换，然后剩下的链表（从第三个节点开始）交给递归函数继续处理。也就是说，swapPairs(node)永远返回“从 node 开始、两两交换后”的新头。这个函数定义一旦清晰，代码就很好写了。

迭代的思路则是用一个 prev 指针串起已经处理好的部分，每次循环处理一对节点，处理完以后 prev 向后移动两位，直到没有成对的节点为止。迭代版本的关键是引入 dummy 哑节点来处理“头节点变化”的问题。

关于选型，我的建议是：理解用递归，面试写迭代。递归在理解清楚之后代码确实只有五六行，但很多人在边界条件和返回值上翻车；迭代虽然代码长一点，但每一步都看得见、调得动，更稳妥。后面两章我分别把两种方式拆开讲清楚。

2. 递归解法：把大问题拆成“反复出现的小问题”

2.1 递归基和返回值的确定方法

递归最难的不是写代码，是定义清楚“函数到底是干嘛的”。很多教程上来就直接给代码，读者看完感觉懂了，自己一写就卡住，核心原因就是没有先定义函数的语义。

对于这道题，我习惯这样定义：swapPairs(head)表示“以 head 为起点的链表，从 head 开始两两交换相邻节点，并返回交换后链表的头节点”。

在这个语义下，递归基是什么？当 head 为 null，或者 head.next 为 null 时，链表没有成对的节点可以交换，所以原封不动返回 head。这就是递归的出口。注意这里不能只写head == null，因为单节点链表也需要返回它本身。

有了这个定义，递归的每一步就变得非常机械：拿到 head 之后，先看 head.next 存不存在。如果不存在直接返回 head。如果存在，那么新头 newHead 一定是 head.next，这一点不依赖后面的任何结果，可以直接确定。

然后要解决的是两个问题：第一，head 要指向谁；第二，newHead 要指向谁。head 应该指向“第三个节点开始，两两交换后的头”，这正好就是swapPairs(newHead->next)的返回值。newHead 则应该指向 head。最后返回 newHead，整个函数就结束了。

2.2 递归步骤的跟踪演示

文字描述比较抽象，我用1->2->3->4->null走一遍完整流程。

调用swapPairs(1)。head 是节点1，head.next 是节点2，不满足递归基。newHead = 2。接着调用swapPairs(3)。

swapPairs(3)：head 是节点3，head.next 是节点4，newHead = 4，调用swapPairs(null)。swapPairs(null)直接返回 null。于是节点3的 next 指向 null，节点4的 next 指向节点3，返回 4。

回到swapPairs(3)这一层，返回值是节点4。也就是“从节点3开始的链表，两两交换后”的头节点是4。注意此刻局部链表已经是3->4变成了4->3，后面还要接到节点1后面。

回到最外层swapPairs(1)：head(节点1) 的 next 指向swapPairs(3)的返回值，也就是节点4。然后 newHead(节点2) 的 next 指向节点1。整个链表从1->2->3->4变成了2->1->4->3，返回节点2。

跟踪一遍你就会发现递归的神奇之处：每一层只需要处理“两个节点 + 一个递归结果”，其余全部交给递归去完成。子问题的规模是 n-2，递归深度在最坏情况下是 n/2，对于长度正常的链表完全没问题。

2.3 递归版本代码与复杂度分析

递归版本的 C++ 代码如下：

class Solution { public: ListNode* swapPairs(ListNode* head) { // 递归基：没有节点或只有一个节点，无法交换 if (head == nullptr || head->next == nullptr) { return head; } ListNode* newHead = head->next; // 第二个节点会成为新头 head->next = swapPairs(newHead->next); // head 接上后续交换结果 newHead->next = head; // 新头指向原第一个节点 return newHead; } };

时间复杂度是 O(n)，因为每个节点都被访问了一次；空间复杂度是 O(n)，这里的 n 不是节点数量那么简单，而是递归调用栈的深度，最坏情况下深度为 n/2，也就是说会有 n/2 层函数调用帧。虽然 n/2 也算 O(n)，但要注意当链表特别长（比如几百万个节点）时，递归版本有可能爆栈，这也是迭代版本在实际工程中更常见的原因之一。

Python 版本更短：

class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head new_head = head.next head.next = self.swapPairs(new_head.next) new_head.next = head return new_head

2.4 递归写法最常见的失误点

我见过最多的问题是递归基写错。有人只写if (head == nullptr) return head;，结果链表是1->2的时候，函数进入第二层调用swapPairs(nullptr)，返回 nullptr，然后外层 head(节点1) 的 next 被置成 nullptr，原链表直接被切断，输出只剩一个节点。这种错误在 OJ 上表现得很明显——输出长度变成原来一半，而且最后少了一个节点。

还有一个失误点是交换顺序颠倒。有人先写newHead->next = head，再写head->next = swapPairs(newHead->next)。看起来差不多，实际上因为此时 newHead->next 还是节点3，递归调用swapPairs(节点3)没问题，但如果先让 newHead->next = head，就相当于把节点2指向节点1，而节点1还指向节点2，形成环，后面递归处理的是谁就完全乱套了。所以建议严格按“先断后面的链，再接前面的链”的顺序来。

提示：写递归前先在心里回答三个问题——这个函数的返回值是什么？递归基是什么？子问题是什么？能清晰回答再动笔。

3. 迭代解法：哑节点 + 三个指针稳稳推进

3.1 哑节点（dummy）为什么是必需品

迭代写法的第一个关键决策就是哑节点。哑节点就是一个不存业务数据的额外节点，它的 next 指向原链表头。为什么要它？因为两两交换之后，原来的第一个节点不再是新链表的头，原来的第二个节点变成了头。如果你直接用 head 指针去遍历，最后返回的时候你会发现根本不知道新头是谁。

有一种做法是保存一个变量记录第二个节点，比如ListNode* newHead = head->next;，然后遍历交换，最后返回 newHead。这样可行，但是代码里要多一个分支判断，而且如果链表为空或只有一个节点，newHead 的取值要特殊处理。哑节点把“头节点会变”的问题统一成一个模型：不管链表怎么变，dummy->next始终指向当前链表的新头，遍历过程中我们只需要关心 prev 指针，不需要额外维护头节点变量。

这里还有一层细节：哑节点不一定要显式 new 一个对象，也可以用栈上变量ListNode dummy(0); ListNode* prev = &dummy;。但为了方便，绝大多数题解都直接ListNode* dummy = new ListNode(0);。注意如果用 new，按面试规范理论上要释放，不过 LeetCode 的评测环境不会计较这种内存泄漏，面试时口头提一句“实际工程里要记得释放”就行。

3.2 三指针交接的完整秩序

迭代的核心是三个指针：prev 指向已经处理完部分的最后一个节点，first 指向待处理的第一对里的第一个节点，second 指向第一个节点后面的那个节点。每次循环要做的事情可以概括成四步。

第一步，确认还有成对的节点。条件是prev->next和prev->next->next都不为空。这个判断很关键，它保证了 first 和 second 都是有效的，不会出现空指针访问。

第二步，用 first 和 second 把两个节点单独拎出来。ListNode* first = prev->next; ListNode* second = first->next;。

第三步，重新连线。顺序是这样的：

first->next = second->next; // 1. 第一个节点指向后一段的头 second->next = first; // 2. 第二个节点反过来指向第一个节点 prev->next = second; // 3. 前一段的尾部指向新的头

这三条线连完，一对节点就换好了。为什么顺序不能乱？如果先执行prev->next = second，此时 prev 已经指向 second，那么再用 first 和 second 原来的关系去操作 next 就不会出问题；但如果你先执行second->next = first，此时 second 还挂在 prev 后面，链路上没问题，可是如果后续还想通过 prev->next 访问链表，得到的还是 second，容易混淆。最稳妥的方式就是上面这个顺序，每一步都基于上一步结束后的状态，不会产生覆盖。

第四步，移动 prev。交换完成后，prev 应该移动到这一对节点中的第二个位置，也就是原来的 first 位置。因为此时 first 已经在 second 的后面了。prev = first;。注意这一步很多人写错成prev = second，那样的话下一轮循环会把已经处理好的部分再处理一遍，导致死循环或错乱。

完整代码：

class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* prev = dummy; while (prev->next != nullptr && prev->next->next != nullptr) { ListNode* first = prev->next; ListNode* second = first->next; first->next = second->next; second->next = first; prev->next = second; prev = first; } ListNode* result = dummy->next; delete dummy; // 工程习惯，LeetCode上可省略 return result; } };

3.3 循环条件的两种写法与边界对比

循环条件有几种等价写法，我列出来对比一下，方便你一眼看懂别人的题解。

• 写法 A：while (prev->next != nullptr && prev->next->next != nullptr)，这是最直观的，直接表达“后面还有两个节点”。
• 写法 B：while (cur != nullptr && cur->next != nullptr)，其中 cur 是当前节点，这种写法要记得循环末尾把 cur 往后移两个节点。
• 写法 C：for (ListNode* cur = dummy; cur->next && cur->next->next; cur = cur->next->next)，这是把条件判断和指针移动都塞进 for 里，代码紧凑，但新手容易看不懂。

边界情况对比表格：

奇数长度链表的处理是这题比较容易被问到的一个点。比如1->2->3，前两个交换变成2->1->3，最后的 3 是落单的，它不会被交换，但会保留在链表尾部。循环条件的设计天然保证了这一点，不需要额外写 if 判断。这也是用prev->next->next而不是用其他条件的好处——不会越界访问。

3.4 空间复杂度对比与内存细节

迭代版本的空间复杂度是 O(1)，只用了几个指针变量，不管链表多长，额外空间都恒定。这一点在面试中经常作为“递归 vs 迭代”选择的理由被问到，答案就是：递归简洁但空间 O(n)，迭代略长但空间 O(1)。

内存细节上还有两个小坑。第一，如果用了new ListNode(0)分配哑节点，在 LeetCode 上不释放没问题，但如果你在本地写完整程序，在 return 之前释放 dummy 是必要的。注意释放后不要再用 dummy，直接把 result 返回就行。第二，链表节点本身是评测系统给好的，我们不能也不应该去 delete 那些节点，否则会造成二次释放问题。

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

4.1 空指针异常的三种典型现场

空指针异常是链表题最常见的报错，这题也不例外。归纳起来有三种典型现场。

第一种是访问 nil 的 next。比如条件写成while (prev->next->next != nullptr)而忘了先判断prev->next是否为空。当链表为空时，prev->next 是 null，再去访问 null->next 直接崩溃。正确的写法是 && 短路：prev->next != nullptr && prev->next->next != nullptr，先确保 prev->next 不为空，才去访问它的 next。

第二种是递归版本里交换顺序搞错导致的访问混乱。比如在递归中先执行head->next->next = head之类（虽然一般不会这么写，但变形题里会出现），破坏了后续指针，再递归调用时就访问到了诡异的地址。

第三种是在迭代循环里没有在开头重新读取 first 和 second。有同学会想省变量，直接用 prev->next 去操作，结果因为 prev->next 在中间被改掉了，后面的步骤全错。调试方法很简单，在循环开头打印prev->next->val和prev->next->next->val，跑几个用例就能发现问题。

4.2 死循环与链成环的排查方法

成环是链表题里比较隐蔽的问题。表现是评测时超时（TLE），因为 while 循环永远走不完。典型的成环原因有两个。

原因一：prev 移动错误。上面提过，如果把prev = first写成prev = second，那么下一轮循环的 prev->next 还是 first，此时 first 和 second 已经被交换过了，但 prev 还停在原位置，第二轮又会把同一对节点交换回去，形成来回震荡，或者死循环。

原因二：连线的覆盖顺序不对。如果在迭代中先执行first->next = second（把第一个节点指向第二个节点，而不是第二个节点的下一个），当链表是1->2->3->4时，节点1指向节点2，节点2指向节点1，这两个节点就形成了一个环，循环遍历永远出不来。

排查成环问题，可以写一个辅助函数打印链表，设置步数上限，比如最多打印 10 个节点，发现重复值或步数到了就停下来。实际工作中我经常用这种方法快速定位是哪个节点的 next 被错误设置。

4.3 奇数长度链表与单节点用例的自测清单

我在面试前总结过一组自测用例，任何链表题我都先跑这组，能过滤掉百分之八十的边界错误：

• 空链表：head = null
• 单节点链表：1->null
• 双节点链表：1->2->null
• 三节点链表：1->2->3->null
• 四节点链表：1->2->3->4->null
• 长链表：1->2->3->4->5->6->null

为什么一定要有三节点和四节点？因为三节点覆盖“奇数长度时最后一个节点保持不动”的场景，四节点覆盖“完整交换两对后返回新的头”的场景。很多新手只测试双节点和四节点，漏了三节点，结果奇偶处理错了都不知道。

我在本地调试时经常用 Python 的 list 转链表的辅助函数：

def build_linked_list(arr): dummy = ListNode(0) cur = dummy for x in arr: cur.next = ListNode(x) cur = cur.next return dummy.next def linked_list_to_list(head): result = [] cur = head while cur: result.append(cur.val) cur = cur.next return result

然后就是简单的断言测试：

assert linked_list_to_list(swapPairs(build_linked_list([1,2,3,4]))) == [2,1,4,3] assert linked_list_to_list(swapPairs(build_linked_list([1,2,3]))) == [2,1,3] assert linked_list_to_list(swapPairs(build_linked_list([1]))) == [1]

4.4 对比不同语言写法的差异

这道题我至少用 C++、Python、Java 三种语言写过，差异主要在三处。

第一处是空指针的表示。C++ 是 nullptr，Java 是 null，Python 是 None，条件判断写法不同，但逻辑一样。Python 里not head or not head.next这样的写法很常见，注意 Python 的 or 和 and 是短路求值，顺序不能颠倒，不然空链表时访问 head.next 会抛异常。

第二处是递归的栈行为。C++ 默认栈容量较小，递归深度太大的时候容易爆栈，但 LeetCode 的测试数据不会把这道题的链表构造到那种规模；Python 则默认有递归深度限制（大约 1000 层），这道题的递归深度是 n/2，链表超过 2000 个节点就可能遇到 RecursionError。LeetCode 官方测试约束里链表长度不超过 100，所以没问题，但如果你想在本地用 Python 测试一个很长的链表，记得先sys.setrecursionlimit调大，或者干脆用迭代版本。

第三处是哑节点的创建。Java/C++ 都是显式 new 一个对象，Python 直接dummy = ListNode(0)，差异不大。真正要注意的是 Java 里 ListNode 的构造函数重载写法，不同写法初始化方式不同，容易在本地编译时踩坑。

class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode first = prev.next; ListNode second = first.next; first.next = second.next; second.next = first; prev.next = second; prev = first; } return dummy.next; } }

5. 从这道题延伸出去的五个变体

5.1 K 个一组翻转链表

两两交换是 K 个一组翻转链表（LeetCode 25 题）的简化版，后者的 K 等于 2。这个扩展我在面试里被问过不止一次，值得单独说一下思路。

K 个一组翻转的核心是要先在每一组内做局部翻转，再把组与组之间接起来。递归写法里，可以先遍历 K 个节点，找到这一组的第 K 个节点作为 newHead，然后翻转这一组的前 K 个节点，再递归处理从第 K+1 个节点开始的后半段，最后把翻转后的这一组尾部接到递归结果上。迭代写法则需要先统计总长度，然后按照长度分批次翻转，每批结束后更新 prev。相比之下，两两交换的循环条件while(prev->next && prev->next->next)只适用于 K=2，扩展到 K 时循环条件要改成“当前组剩余节点数是否大于等于 K”，通常用一个计数器来判断。

这道题的难度跳跃在于，翻转一组比交换两个节点多了一步：找到组内新的头、翻转时保持组内顺序正确、以及组与组之间的连接。但如果你把两两交换的递归语义搞清楚了，K 个一组翻转变成的只是“把两个节点交换”变成“把 K 个节点翻转”，核心还是那三个问题：返回值是谁、递归基是什么、子问题是什么。

5.2 允许交换值时该怎么做

如果题目改成“只交换相邻节点的值”，解法就简单很多：遍历链表，每次把连续两个节点的 val 交换一下，然后 cur 向后移动两位。这个写法的时间复杂度还是 O(n)，但空间复杂度为 O(1)，代码更短。它适合的面试场景是：面试官想考查你对“值交换 vs 指针交换”的理解，或者把题目难度降到热身级别。

写值交换版本的时候有个小坑：交换完两个节点的值之后，cur 要移动两位，不能只移动一位，否则会重复交换第二次。有人写成cur = cur->next->next，但当链表剩余节点不足两个时，cur->next 可能为空，需要先判断。稳妥的写法是先检查 cur->next 和 cur->next->next 是否为空，再用临时变量 next_pair 保存后一对的位置。

5.3 三指针模板在环形链表中的应用

两两交换用的“prev + first + second”三指针模型，在链表类题目里属于高频模板。环形链表的插入、删除节点、链表排序里的节点交换，本质上都是“当前节点的前驱 + 当前节点 + 后继”三个节点的指针重连。学会这道题的三指针推进逻辑，对做其他链表题有很大帮助。

我自己的体会是，三指针最重要的是“处理完一对后，prev 一定要停在正确位置”。这个“正确位置”在交换类题目里是第一对中的后一个节点（也就是新对的前一个节点），在删除类题目里是被删除节点的前驱，在反转类题目里则是当前新链表的尾节点。每次写完循环体，都先画一遍指针变化的图，再确定 prev 应该指向哪里，这一步想清楚了，大部分链表题都能写对。

5.4 面试现场的表达策略

最后补充一点面试技巧。被问到这道题时，不要上来就敲代码。先说思路，我一般会这样组织表达：先指出这道题的核心是相邻两节点交换，难点在于头节点可能变化，所以我用哑节点来统一处理；然后说我有递归和迭代两种思路，我选迭代，因为空间复杂度是 O(1)，代码可控；再说清循环条件是后面还有两个节点，交换的步骤是 first 连到 second 的下一个，second 连到 first，prev 连到 second；最后提一句奇数长度的时候末尾节点不参与交换。

这样表达的好处是，面试官能清楚看到你的思路层次：数据结构的理解（头节点变化）、复杂度分析（递归 O(n) vs 迭代 O(1)）、编码细节（循环条件与连线顺序）、边界处理（奇数长度）。哪怕代码没有一次写对，这个表达框架也能帮你拿到不少分。

我个人的刷题习惯是：每道链表题，都强制自己把递归和迭代各写一遍，然后用自测用例跑通，最后再在白纸上手写一遍。这道两两交换的题目，我前后也写了不下十遍。你会发现，前几遍总是会在递归基或者 prev 移动上卡一下，但练到后面，三指针的顺序已经形成肌肉记忆，写起来一气呵成。这道题本身不难，但它是一个很好的链表操作模板，把它的边界条件和指针交接逻辑吃透，后面的反转链表、K 个一组翻转、LRU 缓存这些题都会顺手很多。建议你今天就把两种写法都在编辑器里过一遍，跑我上面给的自测用例，跑通了就算真正掌握了。