昨天帮团队做链表专题分享一个平时写业务很溜的同事问了我一句LeetCode 24 题我看了题解能看懂自己一写就丢节点这道题到底难在哪 这个问题其实问到了点子上。Leetcode 24. 两两交换链表中的节点在题单上标着 Medium但它最难的地方从来不是思路而是你以为你想清楚了一动手指针就乱飞。这题非常适合拿来检验链表基本功尤其是用 JavaScript 写的时候引用操作的直觉对不对跑几个边界用例立刻现原形。这篇文章就把这道题完整拆一遍递归和迭代两个主流解法逐行讲透附带我实际调试时用到的打印工具、边界用例矩阵以及从这题延伸出去的 K 个一组翻转思路。适合正在准备算法面试的人也适合刚学到链表、对 next 指针绕来绕去感到头大的前端开发者。1. 两两交换考的不只是交换先把链表的基本操作闭环说清楚1.1 数组交换和链表交换的差异很多人在数组里做交换做习惯了下意识会觉得两两交换就是把两个节点对调一下。数组交换确实简单[a, b] [b, a]或者经典的临时变量三步本质上是搬运数据。链表不一样。链表节点之间的关系不是位置相邻而是引用指向。每个节点只有一个val和一个nextnext保存的是下一个节点的引用JavaScript 里就是对象引用。交换两个相邻节点实际要做的是重新编排四个角色之间的关系前驱节点、第一个节点、第二个节点、后继节点。举个例子链表是1 - 2 - 3 - 4要交换 1 和 2。如果只是把节点里存的val从 1 换成 2、2 换成 1得到2 - 1 - 3 - 4从输出看确实对了。但这里有个本质问题你只是做了数据搬运节点本身的物理关系没有变一旦这个节点还挂着其他属性比如指向另一个数据结构的索引或者题目改成K 个一组翻转这种交换值的思路立刻失效。所以刷这题的正确姿势是操作next指针而不是操作val。1.2 交换一对节点你必须同时掌握四个引用链表的节点之间是通过next串起来的交换两个相邻节点本质上要回答一个问题这两个节点从当前位置摘下来之后怎么再插回去一个完整的两两交换操作会涉及四个角色角色示例作用前驱节点 prev交换 1、2 时prev 是虚拟头节点它的 next 要指向交换后的第一个节点第一个节点 first节点 1交换后变成第二个节点第二个节点 second节点 2交换后变成第一个节点后继节点 next节点 3它等待被 first 指向如果不持有前驱节点prev你就算交换了first和second也没办法让前驱正确连上新的头部。这也解释了为什么头节点很特殊头节点没有前驱。1.3 头节点为什么麻烦普通节点交换前驱天然存在但头节点的前面是null你要么单独为它写 if 分支要么用一个虚拟头节点把头节点也变成普通节点。这也是这道题最容易出 bug 的位置之一。很多人写迭代解法交换逻辑本身没错但head处理不好最后返回的链表头部就不对。后面第 3 节会专门讲dummy哑节点的用法那是最省心的方案。2. 递归解法只处理一对节点剩下交给调用栈2.1 递归的核心观察递归解法的切入点很优雅把链表拆成两部分。前两个节点是一部分后面跟着的一整条链表是另一部分。先递归处理后面的链表让它自己完成两两交换返回一个新的头节点然后再把当前这两个节点也交换一下接上递归返回的结果。这个思路避免了你手动遍历时对指针走向的反复推演因为你只需要关心当前这一对怎么交换。听起来有点像把复杂问题外包给一个和你做一模一样事情的分身分身的子问题规模更小直到链表长度不足两个节点为止。2.2 递归代码逐行拆解直接看代码var swapPairs function (head) { // 终止条件空链表或者只剩一个节点不需要交换 if (head null || head.next null) { return head; } // 记住当前这一对节点的第二个节点 const second head.next; // 递归处理后面的链表返回的是后面链表交换后的新头 const restHead swapPairs(second.next); // 交换当前这一对 // 原来的第二个节点指向原来的第一个节点 second.next head; // 原来的第一个节点指向递归处理完的后半部分 head.next restHead; // 当前这一对交换后新的头是原来的第二个节点 return second; };重点理解这几行swapPairs(second.next)传进去的是第二节点后面的整条链表。比如原始链表1 - 2 - 3 - 4这里传的就是3 - 4。递归函数会把它变成4 - 3并返回节点 4。然后执行second.next head也就是让2 - 1。再执行head.next restHead也就是让1 - 4。最终形成2 - 1 - 4 - 3。每一步都只改变当前这一对两个节点的指针后面的结构在递归返回时已经处理好了不需要你操心。2.3 递归的边界、复杂度和适用场景递归的终止条件必须同时判断head null和head.next null。前者处理空链表后者处理奇数长度链表最后的落单节点。漏掉任何一个都会导致空指针错误或者死递归。时间复杂度是 O(n)每个节点被访问一次空间复杂度是 O(n)因为递归调用栈的深度是 n/2。当链表长度为 100 万时递归深度会达到 50 万层JavaScript 运行时会直接抛出栈溢出错误RangeError: Maximum call stack size exceeded。工程代码里处理超长链表时慎用递归但在 LeetCode 的测试数据规模下这个解法没有任何问题。递归版本的优点是代码简洁、逻辑清晰面试时很好讲。缺点是空间复杂度比迭代高。如果面试官要求 O(1) 空间你就需要切换到迭代写法。3. 迭代解法哑节点三步重连绕开头节点没有前驱的尴尬3.1 为什么哑节点是必需品而非技巧迭代解法里头节点没有前驱这个事必须正面解决。两种做法单独处理头节点交换完再更新head。创建一个哑节点dummy让dummy.next指向原头节点然后从头开始统一操作。我强烈推荐哑节点。它不仅省掉了一个 if 分支更重要的是让循环逻辑对每一对节点完全一致也避免了交换头节点后返回错误指针的低级失误。var swapPairs function (head) { // 哑节点val 无所谓重点是 next 指向真正的头节点 const dummy new ListNode(0, head); let prev dummy; while (prev.next ! null prev.next.next ! null) { const first prev.next; const second first.next; // 步骤一前驱指向第二个节点 prev.next second; // 步骤二第一个节点指向第三个节点防止后半段丢失 first.next second.next; // 步骤三第二个节点指向第一个节点 second.next first; // 移动 prev 到新的前驱位置 prev first; } return dummy.next; };下面是1 - 2 - 3 - 4的完整变化过程用文字模拟每一步的状态初始化dummy - 1 - 2 - 3 - 4prev dummy。第一轮循环prev.next second后dummy - 2 - 1 - 2 - 3 - 4这时 1 和 2 之间还是互相指向的中间状态有环但马上会修正。first.next second.next也就是让1 - 3dummy - 2 - 1 - 3 - 4。second.next first让2 - 1dummy - 2 - 1 - 3 - 4此时前两个节点的交换完成。prev first也就是prev移到节点 1 的位置dummy - 2 - 1 - 3 - 4下一轮从这里继续。第二轮循环处理 3 和 4逻辑完全一样。最终dummy.next返回 2。3.2 指针修改顺序为什么是先连前驱再改内部三个步骤的顺序非常关键。一个常见的错误是先写second.next first再写first.next second.next。第二行里的second.next已经被改掉了引用丢失后半段链表直接断开。我的经验是遵守一个原则在修改任何 next 之前先确定你后面还要用的节点引用已经保存在某个变量里了。标准三步的顺序是prev.next second先把前驱连到 second这样从整体链表来看这一对节点已经换头了。first.next second.next此时second.next仍然指向真正的后继节点还没被改过把它保存到 first 的 next 上。second.next first最后才把 second 和 first 的内部连接翻转过来。如果你更习惯另一种顺序可以先把second.next存进临时变量比如const third second.next这样就不依赖执行顺序了。两种写法都能过但脑子里要清楚核心是别丢引用。3.3 迭代 vs 递归怎么选维度递归迭代空间复杂度O(n)调用栈O(1)代码可读性高思路直观中需要理解 prev 移动超长链表的工程场景可能有栈溢出风险更适合面试讲解难度如果你擅长递归更好讲如果你能把 prev 移动讲清楚也很好我个人会先讲递归版本争取快速沟通思路再用迭代版本展示工程化考量。这是面试刷题的一个常用组合拳。4. 边界用例与排查用打印函数把每一步看穿4.1 给链表写一个体检小工具链表题最头疼的问题是调试。你看不到链表现在长什么样只能靠脑内推演。我的做法是准备一个通用的打印函数每次操作后输出一次链表当前状态function printList(head) { const values []; let current head; let count 0; // 加一个安全上限避免环链表导致死循环 while (current ! null count 10) { values.push(current.val); current current.next; count; } console.log(values.join( - )); }注意我加了一个计数器上限。这里的考虑很实际如果代码有 bug 导致链表成环没有这个限制打印函数会无限循环把调试过程搞得更痛苦。加一个 10 次的上限至少能保证控制台不会卡死。使用方式很简单在 swapPairs 函数的关键位置插入打印或者写一个测试函数把每个输入跑一遍直接看输出。4.2 五组必须验证的用例下面这五组用例是我刷链表题必测的覆盖了所有边界类型输入期望输出说明[][]空链表验证终止条件[1][1]单节点验证奇数长度落单[1,2][2,1]最小有效对[1,2,3][2,1,3]奇数长度最后一个节点不参与交换[1,2,3,4][2,1,4,3]偶数长度完整交换有一个细节值得注意奇数长度链表最后一个节点会保持原位。这是由两两交换的定义决定的不是 bug。如果面试官问起来你可以直接说明因为最后只剩下一个节点没有配对对象。4.3 我实际踩过的三个坑坑一忘了移动prev。迭代解法里每一轮结束后必须把prev更新成first。如果忘了循环条件永远基于同一个 prev 判断要么死循环要么只交换第一对。这个错误的隐蔽性在于如果链表刚好只有两个节点代码能跑出正确结果你会误以为写对了。直到测试[1,2,3,4]才发现只交换了第一对。坑二递归终止条件只写了一半。我一开始写过if (head.next null) return head没写head null。看起来只差一个判断实际跑空链表用例时直接报错因为null.next本身就是非法访问。在 JavaScript 里这会抛出 TypeError在 C/C 里就是空指针段错误。链表题的边界判断永远要把空值放在条件表达式的前面并且成对检查。坑三用 JSON.stringify 调试链表。链表节点是互相引用的对象JSON.stringify(head)遇到环状引用会抛错即使没有环它也会把整条链表的结构一次性序列化出来输出冗长完全不适合观察交换过程中的某一步发生了什么。正确做法就是上面那种逐节点遍历打印一步一行清清楚楚。5. 从 24 题延伸开K 个一组翻转和面试官的三个追问5.1 这套方法论在 25 题上的复用LeetCode 25 题K 个一组翻转链表其实就是这道题的超集。当 K 2 时它退化成今天这道题K 3 或更大时核心思路依然是确定这一段的前驱、段内重连、重新接上后继。你在 24 题里练会的先保存引用再改指针在 25 题里依然是主角。区别只在于K 个一组需要先数出这一组是否够 K 个节点然后做一次组内反转。建议刷完 24 题后直接上 25 题你会感觉熟悉很多。5.2 面试官针对这题喜欢追问的三件事追问一你能说说递归的空间复杂度是多少吗可不可以优化 这是考察你是否知道递归调用栈消耗内存。回答时先给出 O(n)然后说迭代版本可以做到 O(1)。追问二如果链表特别长比如几千万个节点递归会出什么问题 这个问题考察工程意识。要答出栈溢出的风险以及迭代版本的长链表优势。追问三如果不想交换节点只交换 val可以吗有什么问题 这就是第 1 节说的值交换陷阱。要明确回答可以但对工程场景不适用且无法推广到复杂节点结构或 K 个一组翻转。5.3 链表操作在真实工程里的位置写业务代码的人可能一年到头碰不到一次手写链表但链表的思想无处不在。前端的虚拟 DOM 的 fiber 架构用链表组织节点浏览器的事件循环队列本质上是链表结构LRU 缓存的一种常见实现也是哈希表双向链表。这些场景里你写不出两两交换这么纯粹的算法但prev、next、临时保存引用、防止引用丢失这套思维完全通用。尤其值得说的是 JavaScript 的引用语义。很多人写链表题时总觉得 JS 里的指针模糊不清其实你只需要抓住一点对象类型的变量保存的是地址赋给另一个变量相当于两个变量指向同一块对象。修改node.next会直接影响所有持有该节点引用的变量。理解了这一点再看链表操作就顺了。最后分享一个我自己的习惯每道链表题写完我会假设自己在熟睡中被叫醒还能不能闭着眼把先保存引用、再修改指针这个流程讲清楚。如果能这道题才算真正过了。LeetCode 24 题不复杂但它值得你多写两遍——一遍递归一遍迭代跑完上面五个边界用例然后把它收进你的链表基本功清单里。