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 是节点1head.next 是节点2不满足递归基。newHead 2。接着调用swapPairs(3)。swapPairs(3)head 是节点3head.next 是节点4newHead 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_head2.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 循环条件的两种写法与边界对比循环条件有几种等价写法我列出来对比一下方便你一眼看懂别人的题解。写法 Awhile (prev-next ! nullptr prev-next-next ! nullptr)这是最直观的直接表达“后面还有两个节点”。写法 Bwhile (cur ! nullptr cur-next ! nullptr)其中 cur 是当前节点这种写法要记得循环末尾把 cur 往后移两个节点。写法 Cfor (ListNode* cur dummy; cur-next cur-next-next; cur cur-next-next)这是把条件判断和指针移动都塞进 for 里代码紧凑但新手容易看不懂。边界情况对比表格场景循环行为返回结果空链表 head nullprev-next 为 null不进入循环dummy-next null单节点链表prev-next 存在但 prev-next-next 为 null不进入循环dummy-next head双节点链表进入循环一次交换后 prev 移动到原 firstdummy-next 原第二个节点奇数长度链表最后一轮循环时只剩一个节点条件不满足停留在原位最后一个节点保持不动奇数长度链表的处理是这题比较容易被问到的一个点。比如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 是 nullptrJava 是 nullPython 是 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 个节点再递归处理从第 K1 个节点开始的后半段最后把翻转后的这一组尾部接到递归结果上。迭代写法则需要先统计总长度然后按照长度分批次翻转每批结束后更新 prev。相比之下两两交换的循环条件while(prev-next prev-next-next)只适用于 K2扩展到 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 连到 firstprev 连到 second最后提一句奇数长度的时候末尾节点不参与交换。这样表达的好处是面试官能清楚看到你的思路层次数据结构的理解头节点变化、复杂度分析递归 O(n) vs 迭代 O(1)、编码细节循环条件与连线顺序、边界处理奇数长度。哪怕代码没有一次写对这个表达框架也能帮你拿到不少分。我个人的刷题习惯是每道链表题都强制自己把递归和迭代各写一遍然后用自测用例跑通最后再在白纸上手写一遍。这道两两交换的题目我前后也写了不下十遍。你会发现前几遍总是会在递归基或者 prev 移动上卡一下但练到后面三指针的顺序已经形成肌肉记忆写起来一气呵成。这道题本身不难但它是一个很好的链表操作模板把它的边界条件和指针交接逻辑吃透后面的反转链表、K 个一组翻转、LRU 缓存这些题都会顺手很多。建议你今天就把两种写法都在编辑器里过一遍跑我上面给的自测用例跑通了就算真正掌握了。