LeetCode第24题——两两交换链表中的节点是我非常喜欢的一道链表入门题。题目要求把链表相邻节点两两交换比如 1 - 2 - 3 - 4 要变成 2 - 1 - 4 - 3并且题目白纸黑字写着不能只改节点内部的值必须真正调整节点之间的指向关系。这题看起来代码量很小但我面试和辅导时见过太多人现场翻车有人把指针更新顺序搞反链表当场变成环有人忘了处理奇数个节点的情况末尾空指针直接报错也有人一听到递归就慌连函数返回什么都说不清。所以我把这题的迭代法、递归法以及带头结点、不带结点的写法全部拆开讲一遍每一步的指针为什么这样走、复杂度怎么算、有哪些高频坑一次说清楚。不管是准备校招还是跳槽用这道题来检验链表基本功性价比极高。1. 题目拆解与核心思路1.1 题目到底在考什么先看输入输出。输入是一个单链表的头节点 head要求把第 1 个和第 2 个节点交换第 3 个和第 4 个节点交换依次往后推如果链表最后只剩一个节点它保持原样不动。几个标准用例head [1,2,3,4] 返回 [2,1,4,3]head [] 返回 []head [1] 返回 [1]。LeetCode 给定的节点数量范围是 0 到 100所以从数据规模上看这道题哪怕写得笨一点也能通过真正的区分度不在这。这道题核心考察三件事第一能不能用指针操作让两个节点在链表里物理换位而不是简单调换 val第二头节点在交换后可能变化你的代码能不能自然处理这种边界第三你能否在迭代和递归两种思路上自由切换。很多新手觉得链表题就是闷头写代码其实它更像手工活——把每个节点想象成积木你做的每一步都是拆开、重接拆装顺序错了整条积木就散架。1.2 为什么不能只交换节点里的值题目里有一个扎眼的约束You must solve the problem without modifying the values in the lists nodes。翻译过来就是不许偷懒把两个节点的 val 对调。为什么因为真实世界里的链表节点往往不只是放一个 int它可能带着数据库主键、业务对象、大块缓存数据。交换节点的物理位置是整体移动而只改值在某些业务场景下会把引用关系搞乱代价完全不同。从面试角度来说如果候选人直接写出这种代码def swapPairs(self, head): dummy head while head and head.next: head.val, head.next.val head.next.val, head.val head head.next.next return dummy跑测试用例也许全都过但这道题的考察意图完全没体现。面试官只需要追问一句如果 val 不是 int而是一个大对象你还愿意这么交换吗基本就露馅了。所以这道题的安全写法只有一条路动指针而不是动值。1.3 迭代法和递归法怎么选先给结论面试时优先讲迭代法尤其是带头结点dummy node的迭代如果面试官追问还有没有别的方法再把递归版拿出来。这个顺序不是拍脑袋定的。迭代版空间复杂度 O(1)不依赖调用栈是工程里更普适的做法递归版代码虽然短空间复杂度却是 O(n)极端情况下有栈溢出风险。但从理解链表递归结构的角度递归版又非常值得吃透。它把一个大问题切分成处理当前两个节点 交给子函数处理剩下的链表这种分治思维以后刷二叉树、刷回溯算法完全是同款。我不建议只背一种写法两版都写熟才算真正掌握这道题。2. 迭代法哨兵节点与指针顺序详解2.1 为什么几乎所有解法都用 dummy 节点带头结点也就是 dummy node几乎是链表题里最常用的技巧。它的核心价值一句话让头节点和其他节点享受同样的待遇避免因为头节点要被换掉而额外写一堆分支判断。这道题里链表头是 1两两交换后新头变成 2。如果不引入 dummy你必须在处理完第一对之后单独把 head 更新成 2。单看这一步不算特别麻烦但如果把问题升级成K 个一组翻转每组头尾都要变没有 dummy 根本写不下去。dummy 的通常做法是新建一个节点令 dummy.next head再用一个 prev 指针从 dummy 出发向后遍历。不管链表最终变成什么样你只需要返回 dummy.next 就一定是正确的新头。我在自己项目里处理链表结构时也一直沿用这个习惯把边界情况统一化让代码从第一行开始就是主逻辑而不是到处塞 if (head xxx) 这种雷区。2.2 迭代法标准实现与逐行解读LeetCode 的 ListNode 定义平台已经给好一般长这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next迭代版的完整实现如下class Solution: def swapPairs(self, head: ListNode) - ListNode: dummy ListNode(0, head) prev dummy while prev.next is not None and prev.next.next is not None: first prev.next second prev.next.next # 第一步让 prev 指向 second prev.next second # 第二步让 first 接管 second 后面的链表 first.next second.next # 第三步让 second 指向 first second.next first # 第四步移动 prev 到 first处理下一对 prev first return dummy.next先看循环条件while prev.next is not None and prev.next.next is not None。它保证当前至少还有两个节点可以交换。如果链表为空prev.next 是 None循环不进入如果链表只有一个节点prev.next 存在但 prev.next.next 是 None循环同样不进入。这个条件写对空指针问题就已经消灭一半。进入循环后first prev.next和second prev.next.next分别取到当前对的第一、第二个节点。我推荐的执行顺序是先让 prev 指向 second再让 first 接管 second 后面的链表随后让 second 指向 first最后移动 prev。这样做的原则是——当你准备修改某个节点的 next 时先想清楚它原本指向的节点后面还有没有谁需要被抓住。2.3 指针顺序理解与现场验证方法很多人会反复问为什么第二步first.next second.next要在第三步second.next first之前我用一个生活类比来解释。想象队列里两个人要换位置a 手里拉着后面的 cb 手里拉着 a。如果先把 b 的手从 a 身上松开让 a 转身去抓 c最后再让 b 反手抓住 a这个顺序一点都不能乱。链表节点也是一样每个节点只有一个 next 出口你在断开一条引用之前必须确保之后还需要访问的那个节点已经有人接管否则那一段链表就丢了。实际操作里我建议画图验证。处理 1、2 节点时原始引用关系是 dummy.next 1、1.next 2、2.next 3。你拿纸笔画三个盒子每执行一个赋值就剪掉一条线、画上一条新线。做完以后应该得到 dummy.next 2、2.next 1、1.next 3。不用多坚持画三张图指针操作就变成肌肉记忆了。我带新人时一直强调链表题不画图就写代码等于闭着眼开车。还要记住一个判断标准如果执行完某一步发现两个节点同时指向同一个 follower这不一定是 bug因为后续指针修改会把它纠正过来。真正的 bug 只出现在两种情况你丢掉了某个节点的唯一引用或者链表中形成了环。带着这个标准去检查代码定位会快很多。2.4 不用哨兵节点的写法边界处理的代价为了真正理解哨兵节点解决了什么问题我建议你尝试写一版不带 dummy 的迭代。代码如下class Solution: def swapPairs(self, head: ListNode) - ListNode: if not head or not head.next: return head new_head head.next prev None cur head while cur and cur.next: nxt cur.next cur.next nxt.next # 先接管下一对的起始节点 nxt.next cur # 交换当前两个节点 if prev: prev.next nxt # 把上一对的后半段接到当前新头部 prev cur # 当前这一对的 cur 成为下一轮前驱 cur cur.next # 此时 cur 已经是下一对的起始节点 return new_head这段代码的关键点在于链表头在第一次交换前就已经确定是原 head.next所以要提前存好 new_headprev 一开始是 None处理第一对时不需要接 prev后面的每一对处理完都必须把 prev.next 指向当前对的新头部也就是 nxt。cur cur.next这行不是写错了——上一轮交换体里 cur.next 已经被改成下一对的起始节点所以直接取 cur.next 就能进入下一轮。对比一下两种写法就能发现不带 dummy 的版本多了空链表/单节点特判、提前保存 new_head、第一轮不接 prev 的分支代码复杂度明显上升。dummy 版把这些边界全部抹平了。以后遇到链表的题我的默认操作就是先加 dummy除非题目明确限制不能用额外节点。3. 递归法子问题拆解与代码逻辑3.1 递归函数怎么定义才能避免绕晕递归题最忌讳一上来就展开调用栈。正确姿势是先给递归函数一个清晰的定义swapPairs(head)返回的是从 head 节点开始经过两两交换之后的新链表头。有了这个定义后面的逻辑全部基于它推演。假设当前链表是 1 - 2 - 3 - 4。我们要交换的是 1 和 2至于 3 和 4 以及后面所有节点交给递归函数去处理。swapPairs(3)应该返回 4 - 3。然后我们要手动完成的只有三件事让 1 指向递归返回的链表头、让 2 指向 1、把 2 作为本轮新链表头返回。递归函数一旦想清楚这三件事代码自然就浮出来了。边界条件也非常清晰如果 head 是 None说明没有节点如果 head.next 是 None说明只有一个节点它没有对等节点可以交换。两种情况下都直接返回 head。这两个判断同时覆盖了空链表和奇数长度链表递归不会出错。3.2 递归实现与执行过程模拟递归版代码非常短class Solution: def swapPairs(self, head: ListNode) - ListNode: if not head or not head.next: return head second head.next head.next self.swapPairs(second.next) second.next head return second我们拿 1 - 2 - 3 - 4 完整推演一遍第一层调用 swapPairs(1)second 2于是调用 swapPairs(2.next)也就是 swapPairs(3)。第二层调用 swapPairs(3)second 4于是调用 swapPairs(4.next)也就是 swapPairs(None)。第三层 swapPairs(None) 直接返回 None。回到第二层head.next 被赋值为 None这一步把 3 和 4 之间的旧链断开随后 second.next head也就是 4.next 3第二层返回 4。此时第二层返回的链表段是 4 - 3。回到第一层head.next 接上第二层返回的 4于是 1 - 4 - 3随后 second.next head也就是 2.next 1第一层返回 2。最终链表是 2 - 1 - 4 - 3。这段推演里最值得注意的点是第二层中head.next None这一步。它看起来奇怪却恰好防止了死循环。如果不先把 3 和 4 断开等到执行 4.next 3 时链表就会形成 3 - 4 - 3 的环。3.3 递归的空间开销与尾递归追问迭代版空间 O(1)递归版空间 O(n)这个结论几乎所有题解都会写。但面试官更想听的是你能不能解释清楚为什么这不是尾递归。尾递归的定义是递归调用发生在函数返回前的最后一步编译器或运行时可以复用当前调用栈把空间退化到 O(1)。本题递归版的最后一行虽然写的是 return second但 return 之前还有两条语句head.next self.swapPairs(second.next) 和 second.next head。其中递归调用发生在整个函数中间调用完还得继续修改指针当前栈帧的局部变量和返回地址都不能释放更谈不上尾递归优化。如果面试官顺着问链表特别长怎么办正面回答就是改用迭代版。LeetCode 这道题 n 最多 100递归深度 50 以内完全无所谓但真实场景里如果链表有几万个节点递归写法随时可能爆栈。面试时能把迭代和递归的取舍讲清楚比单纯把代码跑通要有区分度得多。4. 多语言实现与复杂度对照4.1 Java / C / Go 的参考实现前面示例以 Python 为主这里补一下其他主流语言的迭代实现。Java 版和 Python 的思路完全一致只是把 None 换成 nullclass 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 a prev.next; ListNode b prev.next.next; prev.next b; a.next b.next; b.next a; prev a; } return dummy.next; } }C 版要注意 ListNode 的结构体定义以及 dummy 节点可以直接放在栈上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) {} }; class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; while (prev-next ! nullptr prev-next-next ! nullptr) { ListNode* a prev-next; ListNode* b prev-next-next; prev-next b; a-next b-next; b-next a; prev a; } return dummy.next; } };Go 的写法几乎是把 Java 语法翻成 Go 风格func swapPairs(head *ListNode) *ListNode { dummy : ListNode{Next: head} prev : dummy for prev.Next ! nil prev.Next.Next ! nil { a : prev.Next b : prev.Next.Next prev.Next b a.Next b.Next b.Next a prev a } return dummy.Next }可以看出只要理解了四步指针操作换语言只是语法差异。我个人习惯是平时用 Python 快速验证思路面试用 Java、C 或 Go因为主流后端岗位还是以静态语言为主写起来更贴近工程环境。递归版在 Java 里同样简短其他语言照葫芦画瓢就行class Solution { public ListNode swapPairs(ListNode head) { if (head null || head.next null) return head; ListNode second head.next; head.next swapPairs(second.next); second.next head; return second; } }4.2 时间复杂度与空间复杂度怎么跟面试官讲清楚时间复杂度 O(n) 最好解释。迭代法每一轮处理一对节点n 个节点差不多有 n/2 轮每轮都是常数次指针赋值整体 O(n)。递归版每个节点也只会作为某个递归层的 head 或 second 被操作一次同样是 O(n)。空间复杂度要分开说。迭代版额外只用了 dummy、prev、a、b 这几个指针链表多长临时变量个数都不变所以空间 O(1)。递归版的调用深度等于链表段的处理层数约 n/2 层每一层都要保存局部变量和返回信息空间 O(n)。面试表达可以组织成一句话迭代版 O(n) 时间、O(1) 空间递归版 O(n) 时间、O(n) 空间因为递归深度是链表长度的一半量级。工程中如果链表长度不可控我选迭代。这句话说完复杂度部分基本就满分了。4.3 实践中的代码可读性选择代码可读性经常被刷题的人忽略但它是面试评分里的隐形加分项。我的习惯是变量命名用 a、b、prev 而不是 p、q、temp每三步操作配一句注释说明这一步在做什么循环条件写成prev.next ! null prev.next.next ! null比只写while (prev.next prev.next.next)在语义上更明确虽然效果一样。实际项目里的链表节点可能比 LeetCode 的复杂得多比如双向链表的 Node 会同时有 prev 和 next 两个指针节点里还携带业务字段。两两交换这题虽然是单链表但你把它写顺手之后再去做双向链表版本的交换核心思路完全一致先接管旧引用再调整双向指针最后移动前驱。5. 高频错误与调试技巧5.1 三个最容易踩的坑及修复我把辅导时见过最多的三类错误整理成一张表错误类型错误示范后果修复方法循环条件漏判空while (prev.next.next)空链表或单节点直接空指针异常写成prev.next ! null prev.next.next ! null指针更新顺序错误先b.next a再a.next b.nextb.next 已被改成 aa.next 指向自己链表成环必须先a.next b.next再b.next a只交换值只交换a.val和b.val违反题意暴露理解短板用指针重连节点第一类坑最普遍原因是把循环条件写得太随意。链表操作里严格判空不是怂是基本素养。第二类坑最隐蔽因为简单用例可能碰巧不触发死循环链表一变长必爆。第三类坑属于方向性错误代码就算能跑通也没有意义。递归版还有一个特殊坑边界判断如果只写if (head null)而漏掉head.next null单节点链表在递归体里会对 None 解引用直接抛异常。两个边界必须同时判断。5.2 快速自测的小技巧我从刷 LeetCode 第一天就养成了一个习惯每个链表题都先写好构造和打印函数测试完一眼看出结果对不对。def build_list(values): dummy ListNode(0) cur dummy for v in values: cur.next ListNode(v) cur cur.next return dummy.next def print_list(head): res [] while head: res.append(str(head.val)) head head.next print( - .join(res))自测用例建议固定六个空链表、单节点、两节点、三节点、四节点、五节点。前两个验证边界条件中间三个验证两对、三对交换的结果五节点的用例专门覆盖奇数长度时末尾节点保持不动的场景。这六个用例全过代码基本就稳了。画图也是很值得强调的技巧。很多人链表题出 bug 以后死盯屏幕越盯越晕。我的建议是拿纸笔把节点画成盒子每执行一次赋值就剪掉一条线、补上一条新线。坚持几次之后你会发现肉眼调试的速度比在 IDE 里打断点打日志还要快。5.3 把交换框架固化成模板刷题不能每次重新推演应该把高频操作固化成模板。这道题的模板可以提炼成五步建 dummyprev 指向 dummy循环条件剩余节点至少两个每次取 a 为 prev.nextb 为 prev.next.next执行固定四步prev.next ba.next b.nextb.next aprev a返回 dummy.next。这个模板不止适用于 swapPairs。LeetCode 25 题K 个一组翻转链表每轮先数出 k 个节点再反转这一段然后用类似逻辑接回前驱。你可以把模板理解成链表重排四步曲——接管前驱、保存后续、翻转指向、移动前驱。有了肌肉记忆遇到链表的变形题会从容很多。6. 题型扩展从两两交换到K个一组翻转6.1 与 LeetCode 25 的关系K2 特例两两交换可以看成K 个一组翻转链表在 K 2 时的退化情况。25 题的描述是给你一个链表每 K 个节点一组进行翻转剩余不足 K 个的节点保持原样。它的难度立刻上了一个台阶因为你需要先确定每一组的边界然后再做区间反转。核心思路仍然基于我们刚练的框架大致流程是从当前节点出发数 K 个节点不够就返回剩余链表够 K 个就把这一段截出来用标准反转链表的方法反转同时记住下一组起点把反转后的头接到前驱后面最后把前驱移动到本组的尾节点。两两交换时 K 2反转两个节点退化成我们上面那一次局部重连所以代码特别简洁。等你把 25 题写顺了回头看 24 题会觉得一切都是顺理成章。6.2 面试官追问还能怎么优化的正确应对思路如果面试官问还有更优的算法吗别慌先把复杂度分析摆出来单链表交换相邻节点每个节点的 next 指针至少要被修改一次所以时间下界就是 O(n)额外空间上迭代版已经做到 O(1)。到达了最优解没有什么更优可言。这时候可以顺势展示思考广度。比如如果题目允许额外空间可以用数组把节点指针全部存下来两两交换数组下标后批量重连 next。但这个方案空间 O(n)并不比迭代好只有在不许改节点内部值、又必须快速随机访问这种特殊约束下才值得考虑。能说清楚为什么这个方案不好才是真正的理解。还可以提一句并发场景真实系统里链表往往被多线程共享两两交换不是单步操作中间状态可能被其他线程读到需要加锁或者使用无锁数据结构。这部分面试里点到即止主动提一嘴能显得你思考的不只是 OJ 层面的算法还有工程落地的复杂性。最后说点我个人的体会。两两交换链表节点我在刷题阶段写过、后来在真实代码里也写过几乎一样的逻辑它不炫技却极其考验人对引用的理解。我建议你把这题的三种写法都手写一遍带头结点的迭代、不带头结点的迭代、递归。写完之后再去做反转链表和 K 个一组翻转你会明显感觉自己更敢碰指针了。面试时如果只够答一种我肯定选带头结点的迭代版把四步操作讲得明明白白如果面试官追问再补充递归顺便解释为什么它没法做尾递归优化。能讲到这个深度链表这道题你就真正过关了。