LeetCode第24题：两两交换链表节点的迭代与递归详解

接触过 LeetCode 的朋友对第 24 题“两两交换链表中的节点”多半不陌生给你一个单链表要求每相邻两个节点交换位置并且不能只改节点里的值。它常被归在链表、迭代法、递归法这个知识聚类下面也是很多“热门 100 题”清单里的常客。它到底在讲什么输入1 - 2 - 3 - 4输出2 - 1 - 4 - 3输入1 - 2 - 3输出2 - 1 - 3。看似只有三五行代码但迭代时 dummy 节点怎么放、递归时先执行还是先改指针、边界条件哪些组合容易崩这些细节几乎能把“是不是真的动手写过链表题”的人筛出来。这篇文章我会按题目拆解、迭代法、递归法、其他实现、常见错误与调试技巧、实战复盘六个部分来讲适合刚刷链表章节的新人也适合面试前想快速复习一遍的老手。这类题不像动态规划那样依赖大量数学直觉它考的就是你对“指针/引用”的掌控以及把循环不变量写清楚的能力。你身边可能有人能不看题解手写出来但让他说清楚为什么那样改指针可能就含糊了。看完这篇我希望你不只是背住代码而是能在白板上把每一步指针变化讲明白。1. 题目拆解与思路全景先别急着写代码1.1 题目到底要求做什么LeetCode 题库里一般这样表述给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部值的情况下完成本题即只能进行节点交换。这里先做两个翻译。第一“相邻的节点”不是指数值相邻而是链表中物理位置相邻第二“只能进行节点交换”是题目的硬约束。很多新手第一反应是“那我交换 val 不就完了”这在大部分在线评测里会因为题目表述被判定为不合规在面试中也基本会被追问“如果不让你改值怎么办”。用例子感受一下[]-[][1]-[1][1,2]-[2,1][1,2,3]-[2,1,3][1,2,3,4]-[2,1,4,3]奇数长度时最后一个节点没有配对对象保持原样挂在一个交换后的节点后面偶数长度时所有节点都会重新排列。这个“奇数长度尾巴怎么处理”是后面所有方案都必须满足的一致约定。1.2 为什么这道题能一直火先说结论它把链表题的几个核心考点压缩成了一个很小的题目。第一头节点位置会变化。因为第一对交换后原来的 head 不再是要返回的头所以面试者要懂得用 dummy 节点消除特判。第二三根指针的重新接线。交换两个相邻节点需要破坏和重建至少三段 next 关系顺序错一步就是死链。第三递归出口和递归公式都很自然。如果你懂得“递归后返回的是当前子链表的新头”这道题的递归实现几乎一行公式就能讲清楚。第四它是进阶题的地基。LeetCode 第 25 题“K 个一组翻转链表”本质上就是本题的通用版本把“每两个交换”变成“每 K 个翻转”。如果本题你还需要画半天图第 25 题会非常痛苦。所以你可以把它理解成“链表指针操作的微型基准测试”。在面试里它不一定作为压轴难题却频繁作为热身题出现目标就是看你基础是否扎实。1.3 先建立一个“局部交换不变量”在写任何代码前我习惯先给所有链表题定义一个“当前状态”假设当前有一个前置节点 prev它后面挂着待处理链表的头部 first而first.next是 second。也就是说我们面对的局部结构是prev - first - second - rest我们的目标是把这一段变成prev - second - first - rest然后继续处理 rest。这个“不变量”一旦固定下来迭代法就很机械每次操作都是同一套三行重连线循环条件只看 rest 是否还至少有两个节点。永远不要在脑里直接想“1 和 2 交换3 和 4 交换”而是把它看成“每次把 prev 后面的两个节点拿出来调个头再放回去”。这两种思维方式差别很大前者容易忽略 prev 怎么连上交换后的第二个节点后者每一次都是一样的动作。2. 迭代法实现用 dummy 节点稳住头2.1 为什么 dummy 是不可或缺的一步先看一个非常容易犯的错直接拿着 head 在循环里把指针换来换去最后却不知道怎么返回新头。因为第一对交换后新的头变成了原来的第二个节点。如果你没有用一个哨兵节点记录位置就必须在循环外做额外的 if 判断代码会变得很啰嗦而且容易漏。dummy 节点解决的就是这个尴尬dummy ListNode(0, head) prev dummy我们让一个永远存在的哨兵节点挂在原链表前面然后全程只操作 dummy 后面的链表。最终答案直接返回dummy.next因为 dummy 本身不参与交换无论链表怎么腾挪它作为“新头的上一个节点”的位置始终是明确的你不需要对“原 head 被换走”这件事做任何特殊处理。这个思想在反转链表、删除倒数第 N 个节点、合并有序链表里都会反复出现并不是这一题专属。面试时主动说出“我用 dummy 来避免处理头节点被换走的情况”通常是个加分项。2.2 三段指针重连的完整推导现在基于不变量prev - first - second - rest写出标准迭代解法class Solution: def swapPairs(self, head: ListNode) - ListNode: dummy ListNode(0, head) prev dummy while prev.next and prev.next.next: first prev.next second prev.next.next first.next second.next second.next first prev.next second prev first return dummy.next逐行解释这一段first prev.next拿到当前对中的第一个节点。second prev.next.next拿到第二个节点。first.next second.next先把 first 接到 rest 上。这一步很关键它把 second 摘下来之前先保住了后面的节点。second.next first让 second 反超指向 first。prev.next second让 prev 连到新的局部头 second。prev first下一轮的前置节点是 first因为 first 已经变成这一对的末尾后面紧跟着 rest。如果你把第 3 步放到最后写先写了second.next first之后first.next second.next时second.next已经被改成 first于是 first 指向自己链表直接成环。我见过太多人在这里翻车建议你背下这个顺序先接 rest再回头链 first最后让 prev 归位。其实很好记——first 原本在 second 前面你至少要在第一步让 first 和 rest 先确立关系才不会丢后续节点。再看 while 条件为什么要写成prev.next and prev.next.next。遍历到奇数长度时最后一轮的 prev 后面可能只剩一个节点比如1 - 2 - 3交换完前两个之后prev 指向 11.next是 3但3.next是 None。此时prev.next存在、prev.next.next不存在循环结束3 正常保留。如果只写while prev.next你会在空节点上访问 next 导致空指针异常。同样的逻辑用 C 写一遍区别只在内存管理ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0, head); ListNode* prev dummy; while (prev-next prev-next-next) { ListNode* first prev-next; ListNode* second prev-next-next; first-next second-next; second-next first; prev-next second; prev first; } ListNode* ans dummy-next; delete dummy; return ans; }如果你的 C 环境不允许这种构造函数也可以分两行写ListNode* dummy new ListNode(0); dummy-next head;效果一样。2.3 迭代方案的复杂度与现场问答时间上每个节点最多被访问常数次所以是 O(n)空间上只用了若干个局部指针所以是 O(1)。这几乎是对“链表重排题”的标准要求。面试官常会追加几个小问题“如果链表有 10 万个节点递归和迭代你选哪个”答迭代理由不是正确性而是递归栈深可能达到 O(n)某些环境下会导致栈溢出。“为什么 dummy 不用参与最后输出”因为 dummy 是我们额外构造的哨兵题目要求的有效节点范围不包含它所以dummy.next就是真正的答案头。“如果要求原地完成这个方案算吗”算。原地是指不额外创建新链表节点而不是不允许使用几个引用变量。我们所有重连都在原有节点之间进行dummy 只是辅助头不是复制节点。真正写现场代码时建议先画一个四节点小图标出 prev、first、second、rest 四个位置再对着图改每个箭头。很多链表面试允许甚至鼓励先画图别觉得不好意思。3. 递归法实现把问题扔给后半个链表3.1 递归公式是怎么来的递归解法的核心思想一句话别一口气处理完整条链表只处理前两个节点后面所有节点通过递归交给同一个函数。假设有一个函数swapPairs(head)它接收一段链表的头节点返回这段链表两两交换后的新头。那么对于前两个节点 first 和 second我们需要first 和 second 要互换位置first 应该接在哪里它应该接在“second 之后那一段已经递归交换完成的新链表”的头上second 应该成为当前这一段的新头。翻译成递归式swapPairs(head) if head is None or head.next is None: return head first head second head.next first.next swapPairs(second.next) second.next first return second这里有个非常容易踩的坑如果先写second.next first再写first.next swapPairs(second.next)由于second.next已经变成 first递归传进去的就不是 rest而是整个又回到 first形成无限递归直接栈溢出。正确顺序必须是先让first.next指向 rest 的递归结果再让second.next first。或者你可以在最开始就用临时变量next_pair second.next把它存起来然后放心改引用。3.2 递归代码与“新头”的理解Python 版本非常短class Solution: def swapPairs(self, head: ListNode) - ListNode: if not head or not head.next: return head first head second head.next first.next self.swapPairs(second.next) second.next first return second为了更直观用一个递归调用栈走一遍1 - 2 - 3 - 4第一层调用swapPairs(1)first1second2然后调用swapPairs(3)。第二层调用swapPairs(3)first3second4然后调用swapPairs(None)。第三层调用swapPairs(None)命中not head返回 None。回到第二层3.next None4.next 3返回 4。回到第一层1.next 42.next 1返回 2。最终接到2 - 1 - 4 - 3正确。注意第二层返回的 4 并不是直接接到某个全局变量上它是通过第一层first.next ...这条语句被接到了 1 的后面。这正是“递归返回的是子链表新头”的含义每次调用向上返回的都是当前段交换后的头部调用方把它当作一个整体接在自己后面。奇数长度时比如1 - 2 - 3第一层swapPairs(3)命中not head.next直接返回 3回到第一层1.next 3然后2.next 1结果2 - 1 - 3末尾的 3 被自然保留。3.3 递归能过但别忽略它的代价递归解法的代码非常简洁面试时先讲递归公式往往能让对方觉得你有抽象能力。但你需要主动补充它的空间代价每递归一层系统栈上就要保存一层调用现场。链表长度是 n 时递归深度大约是 n/2 的量级空间复杂度为 O(n)。如果 n 是百万级某些平台可能直接栈溢出。如果面试官问“递归函数中哪个变量最关键”我会回答second.next。因为只有它保留了 rest 的起始地址整个递归才有一条连续的传递链。你甚至可以在一开始就写tmp second.next然后再做交换class Solution: def swapPairs(self, head: ListNode) - ListNode: if not head or not head.next: return head first head second head.next tmp second.next first.next self.swapPairs(tmp) second.next first return second这样读起来可能啰嗦一点但不容易犯顺序错误。我个人在白板编程时宁可多写一行临时变量也不愿意把正确性押在“思路顺序千万别乱”上。这种防御式写法在项目代码里同样适用围观别人代码时偶尔会看到有人把 next 指来指去最后成环但很少看到有人先存一份 next 还会成环。4. 变体实现与思路对比不只迭代和递归4.1 用栈把每一对拆出来迭代和递归是这道题的标准解但“多种实现方案”还可以聊栈和容器。用栈的思路是因为交换后每一对内部的顺序要反转而栈天然就是先进后出所以可以一次把 first、second 入栈再从栈里 pop 出来。pop 出的顺序正好是 second、first再把它们逐个接到结果链上。def swapPairs_stack(head: ListNode) - ListNode: if not head or not head.next: return head dummy ListNode(0) tail dummy stack [] cur head while cur: if cur.next: stack.append(cur) stack.append(cur.next) cur cur.next.next else: stack.append(cur) cur None while stack: tail.next stack.pop() tail tail.next tail.next None return dummy.next这个做法的时间复杂度同样是 O(n)但空间变成 O(n)并不算最优。它唯一的优点是直观完全靠栈的 LIFO 特性实现“两两反转”不需要手工维护指针顺序。如果面试时你一时紧张忘了标准的 prev 三连先说这种思路作为过渡比卡在原地强。面试官如果追问空间你可以立刻承认“这不是最优我会换迭代法”。不过要注意用这种写法处理奇数长度时单独落单的节点也要入栈再弹出一次。有些初学者会直接tail.next cur把落单节点接上逻辑上没问题但最好保持所有节点都走同一个拼接流程减少分支。4.2 用容器存节点再重排一种能救命但不够优的方案还有一种更直接的做法先遍历链表把所有节点放进数组然后交换数组里的相邻元素再按照数组顺序重建链表。def swapPairs_array(head: ListNode) - ListNode: nodes [] cur head while cur: nodes.append(cur) cur cur.next for i in range(0, len(nodes) - 1, 2): nodes[i], nodes[i 1] nodes[i 1], nodes[i] dummy ListNode(0) tail dummy for node in nodes: tail.next node tail node tail.next None return dummy.next这段代码能正确通过大部分测试但面试时我一般只把它当“思路板”来讲不会当作最终提交。原因很现实它额外使用 O(n) 空间并且偏离了“只能进行节点交换”的题目精氮。可如果面试环境里你有 5 分钟想不出标准指针操作先跑通一个能用的解法再在面试官提示下优化到 O(1) 空间也不失为一种应对压力场景的策略。关键是你要心里清楚这是空间更差的方案而不是把它包装成最优解。4.3 “直接交换节点值”为什么是陷阱我还看到有人这样写cur head while cur and cur.next: cur.val, cur.next.val cur.next.val, cur.val cur cur.next.next return head如果题目允许修改节点内部值这段代码确实能通过。但原版英文题目明确写着“You may not modify the values in the lists nodes”所以提交会报错。更重要的是真实系统里交换值有两个深层问题其他还在引用这些链表节点的代码拿到的还是同一个对象但对象里的值已经和原来对不上这会让外部引用产生诡异的不一致。如果节点除了 val 还包含其他状态字段只交换 val 相当于只搬了一部分状态错误是必然的。面试里如果你先问一句“这道题允许交换值吗”是加分的如果你不问直接交换值面试官很可能现场给你加一个“节点对象还有 id 字段不能改”的额外条件然后看你还会不会写。所以结论要明确本题要求改指针不改内容。4.4 四种方案横向对比实现方案时间复杂度空间复杂度难度推荐度迭代 dummyO(n)O(1)中等面试首选递归O(n)O(n)较低思路展示栈O(n)O(n)简单辅助思考数组重连O(n)O(n)简单不推荐交换值O(n)O(1)最简单题目禁止除了最后一个前四个方案都能做到“不修改节点内部值、只调整指针”只是空间和实现的优雅程度不同。如果你在面试中能列出这样一张对比表说明你不仅知道怎么写还知道每种写法的定位表现会很加分。5. 边界条件、常见错误与调试技巧实录5.1 先写一个能打印的辅助函数链表题犯错的经典场景是脑子觉得对了跑起来以后死循环。我强烈建议大家本地练习时先写一个转换函数把链表打印成数组再看def to_array(head: ListNode): arr [] while head: arr.append(head.val) head head.next return arr def from_array(arr): dummy ListNode(0) tail dummy for v in arr: tail.next ListNode(v) tail tail.next return dummy.next我在调试递归版本时经常在关键位置插入print(head.val)看递归到底从哪里开始崩。一个典型的调试场景是输入[1,2,3,4]递归实现如果死循环多半是因为first.next self.swapPairs(second.next)和second.next first的顺序写反了。打印调用栈能很快发现second.next从 3 变成 1导致永远停在原地。5.2 高频错误清单我归纳了写这题最常见的五个坑每一个都有对应的规避方法。第一循环条件写成while head.next或while current.next。如果链表为空head.next直接空指针。正确写法是同时判断当前节点和下一节点都不为空也就是while prev.next and prev.next.next。第二重连顺序错了。正确顺序是先first.next second.next再second.next first最后prev.next second。如果搞反很容易让后续节点丢失。我用一个口诀记先救 rest再反超最后让 prev 跟上去。第三循环结束后忘记让prev后移。如果prev一直停在 dummy第二次交换会把已经交换好的结构再拆一遍结果看起来像是没交换。标准迭代里每次置prev first因为 first 已经移动到本对的末尾下一次操作就应从这里继续。第四递归版本里没有先保存second.next。你一旦调用递归或修改first.next现场就不一样了。建议最保险的写法永远先把tmp second.next存下来再改引用。第五最后return head。当头节点被交换后head 已经不再是新头。迭代法要返回dummy.next递归法要返回计算出的second。如果有人把递归写成return head就是没理解函数返回值的角色。5.3 建议打一套完整测试用例刷题不能只跑题目给的两个示例。我的本地测试会至少覆盖以下情况空链表[]要返回None。只有一个节点[1]要原样返回。两个节点[1,2]交换后[2,1]。三个节点[1,2,3]交换后[2,1,3]。四个节点[1,2,3,4]交换后[2,1,4,3]。更长一点[1,2,3,4,5,6]检查连续多轮交换。所有节点值相同例如[1,1,1,1]排除依赖值比较的错误。很多人在 LeetCode 上提交失败后发现错不在算法思路而是测试用例覆盖太少。空链表和单节点这两个特判一旦漏掉基本秒挂奇数长度尾巴漏掉也会在[1,2,3]这个用例上现出原形。5.4 如何向面试官展示测试功力有时候面试官不只看你代码能不能跑还会问“你打算测哪些例子”。这时候别只说“我测 1 和 4 两个”。我一般会按“最小、单节点、双节点、奇数、偶数、长链表”的顺序报出来并说明每个用例目的最小用例[]验证空指针安全单节点[1]验证递归出口和迭代循环条件双节点[1,2]验证完整交换流程三节点[1,2,3]验证奇数尾巴不会被错误截断四节点[1,2,3,4]验证连续两次调整后的链接关系。这套回答能让面试官感觉到你不是背题而是真正理解边界。尤其在手写代码环节代码写完还能主动补一句“我可以先拿这几个 case 快速走一遍”往往比急着提交更有好感。6. 实战复盘这道题到底帮你练了什么6.1 指针操作背后的思考抽象回过头来看第 24 题最值得练的不是那三行交换而是“你如何把一次交换看成不变量驱动的反复操作”。我用迭代法时脑子里始终只有一条公式prev - first - second - rest变成prev - second - first - rest。初学阶段我习惯在纸上把四个节点画出来每写一行代码就改一次箭头改完以后再对照预期。练习几次后你会发现自己看链表题越来越快因为所有重排题都离不开“先保存下一个、再断开、再连接”这三板斧。这不是玄学而是因为链表本身就是由“指向下一个节点的引用”构成的。你对引用操作越熟练写其他数据结构题时也越稳。比如合并两个有序链表、删除链表中的重复元素、反转链表区间底层全是同一套引用思维。6.2 我的推荐刷题顺序如果你正准备面试我建议按这个节奏练第一轮只看题解理解迭代和递归两种写法合上题解后空跑一遍1 - 2 - 3 - 4确认每一步指针变化。第二轮不看题解自己从零写重点把循环条件、递归出口、返回值写对。第三轮限时 10 分钟手写并尝试在白板上向虚拟面试官解释为什么 dummy 能避免头节点特判。第四轮做完后继续刷第 25 题“K 个一组翻转链表”把本题的“每两个交换”泛化到“每 K 个一组翻转”。我自己的体验是不先刷第 24 题直接硬啃第 25 题十有八九会卡在“每 K 个一组”的指针细节里而把第 24 题吃透之后第 25 题只是增加了一组循环和一段逆序逻辑思路能顺下来不少。6.3 几个容易被忽略的战略细节最后分享几个带点个人方法论的经验。第一个经验不要在面试一开始就闷头写。链表面试题最忌不画图。哪怕只是在白板上画三个圆圈和两个箭头也能极大降低自己在重连顺序上的脑内负担。我见过太多候选人明明会做却因为省略画图环节而在一个边界上卡了五分钟。第二个经验一定要说复杂度。迭代是 O(n) 时间、O(1) 空间递归是 O(n) 时间、O(n) 栈空间。面试官问完“还有别的方案吗”你把递归和迭代的取舍讲清楚就把一道简单题聊出了层次感。第三个经验如果写了递归一定要主动提“这里空间不是 O(1)”。很多候选人在白板上写递归时被问一句“你这个空间复杂度是多少”就哑火了。提前想好答案答题节奏会完全不一样。第四个经验写代码时要避免用太花哨的写法。比如 Python 里用元组交换head, head.next head.next, head看着很聪明但在要求指针重连的题里并不利于展示你的思考过程。面试手写不是炫技是用最朴素的方式把逻辑讲清楚。6.4 从这一题带走什么LeetCode 24 这种题目看起来简单但它处在链表基础和链表进阶的交界处。你只要在这里稳住后面遇到反转链表、环形链表、合并链表会明显更有底气。我的建议是不要只背代码要把“为什么先接 rest”“为什么 dummy 能解决头节点变化”“递归返回的是什么”这三个为什么真正想明白。我实操下来还有个心得链表题写好之后一定要用“两个节点交换后再交换”的场景走一遍而不是只走完整链条。因为多数错误都发生在“第一轮交换后prev 的位置”上这比验证最终输出更能暴露问题。你也可以把这段检查写成一个小的断言在本地测试里反复跑直到把标准迭代和递归都跑顺。刷题这件事有人追求数量有人追求速度。但就第 24 题而言我更推荐追求“能讲”。当你可以一边画箭头一边说出下一步该改哪条 next并且能回应面试官抛出的空间复杂度追问这道题才算真正刷完了。