★ FEATURED ARTICLE 两两交换链表中的节点是链表类题目里绕不开的一道经典题也是我当年刷了整整三遍才真正敢说“吃透”的题。先纠正一个容易被标题误导的点LeetCode 题库里“两两交换链表中的节点”的编号其实是24104对应的是一道二叉树最大深度的题。这不影响本文的价值——这道题考察的是链表指针操作的基本功很多面试官尤其喜欢拿它来验证候选人到底理不理解“节点引用”这件事。不管是刚开始刷链表的新手还是准备面试想巩固基础的人把这道题彻底弄明白都很有必要。下面我把自己反复踩过的坑、走查过的每一步、面试中被追问过的点按五个部分整理出来。你要是跟着画两遍基本就不会再忘了。1. 先搞清楚这题到底在考什么题号乌龙与边界条件1.1 题号乌龙104和24的误会先说回标题里的“104”。如果你真的去 LeetCode 搜索104看到的是二叉树最大深度而不是链表两两交换。这是当初发题的人可能记错了编号或者从某份资料里复制时搞混了。好消息是题号错了不影响题目本身的含金量。我在实际练习中发现很多人会因为“题号都写不对”而对题目产生疑问其实完全没必要按题目内容来就行。LeetCode 24 的原题描述很简单给定一个链表两两交换其中相邻的节点并返回交换后链表的头节点。注意描述里有一句关键约束不能只是改节点内部的值而是要真的交换节点。这个约束直接把题目从“数组思维”拉回了“链表思维”。很多人第一次做这道题时完全没意识到这句话的分量以为把两个节点的 val 换一下就完事了。后面我会专门讲为什么这个约束才是考点的真正所在。1.2 题目原貌与“不允许只改值”的隐藏考点题目给出的例子很直观输入 1-2-3-4输出 2-1-4-3。输入 1-2-3-4-5输出 2-1-4-3-5也就是链表长度为奇数时最后一个节点保持原位置不参与交换。“不允许只改值”这句话隐藏的考察目标其实是你是否理解链表结构本身。如果允许只改值这道题就退化成了数组里的相邻元素交换和链表这个数据结构没有任何关系。而链表的本质是一连串通过 next 引用串起来的节点所有增删改查操作都发生在“连接关系”上。只改 val 的做法在真实工程里也有问题链表节点往往不止存一个值可能还携带其他字段更关键的是外部可能有引用指向某个节点只改值不会让这些外部引用跟着一起“交换”数据一致性很容易被破坏。所以刷题归刷题这个约束背后是有工程理由的。1.3 四种边界条件一览做链表题边界条件永远是翻车重灾区。这道题我总结了五组用例基本上把它们跑通代码的鲁棒性就有保障了。输入链表期望输出说明空链表空链表指向 head 即可不能访问 head.next单节点 [1][1]没有第二个节点可交换双节点 [1,2][2,1]最简交换场景三节点 [1,2,3][2,1,3]奇数长度末尾节点不动四节点 [1,2,3,4][2,1,4,3]完整的两两交换这五组用例背后其实只有两个边界判断某一步是否存在 second 节点。我把这一节放在最前面是因为后边所有迭代和递归的循环终止条件本质上都在处理这两句边界判断。把这些用例记在脑子里你写代码的时候就有了兜底的验证集。2. 迭代方案dummy节点与三指针固定舞步2.1 为什么没有dummy就要额外处理头节点迭代方案里我第一个要说的不是指针怎么摆而是 dummy 节点。几乎所有链表的“头节点会变化”的题目都需要一个 dummy 来统领全局。什么叫头节点会变化在这道题里输入是 1-2输出是 2-1链表的头节点从 1 变成了 2。如果你没有 dummy函数里就要写一堆 if 来判断“当前交换的这对节点是不是头部这对”最后返回的时候还要单独返回新的头节点。这既容易出错又让代码看起来很不优雅。加上 dummy 之后一切都不一样了。dummy 本身是虚拟节点它的 next 一开始指向 head。在循环过程中dummy 的作用就是充当“头节点前任”的角色让第一对节点的交换方式和后面每一对完全一致。最终返回值直接写 dummy.next 就是新链表的头。虽然 dummy 的 val 随便给个0就行但它不属于目标链表本身只是一个辅助标记。我在练习时见过有人最后返回了 dummy 本身然后死活跑不出正确结果这种低级错误提醒自己注意 dummy 和 dummy.next 的区别。2.2 三指针交换的四个动作与保存后继原则真正的交换逻辑我习惯用三个指针来定位first、second、third。first 是当前要交换的第一个节点second 是第二个节点third 是 second.next也就是后续链表的头。看代码之前先把为什么需要 third 想明白。链表操作有个铁律在修改任何节点的 next 之前必须先想清楚“这个节点改完之后原来指向的地方还找不找得回来”。交换 first 和 second 的过程中至少有两条 next 会被改写。如果不先保存第三根指针改完某条 next 之后原来的后继可能就再也拿不到了。生活中最接近的场景是排队两个小孩要换位置中间牵着一个“引路人”你如果不提前让引路人记住后面的人是谁队列一旦拆开就全散了。具体交换动作我推荐下面四步prev.next second把当前这对节点的前驱接到 second 上second.next first让 second 指向 first两个节点完成交换first.next third让 first 接回后续链表prev first移动 prev 到 first 的位置准备处理下一对。这个顺序不是唯一的但第3步和第2步的顺序绝不能颠倒。如果你先执行 second.next first再执行 first.next third由于 second.next 已经被改成 firstthird 仍然可以通过 first.next 找回吗可以只要 third 在变量里保存着就行。真正危险的是不保存 third而是靠 first.next second.next 这种写法去隐式拿后继因为这时 second.next 可能已经被改掉了。2.3 完整代码与一次手推走查Python 的迭代解法可以写成这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def swapPairs(head): dummy ListNode(0) dummy.next head prev dummy while prev.next and prev.next.next: first prev.next second first.next third second.next # 四步交换 prev.next second second.next first first.next third # prev 前进到 first prev first return dummy.next我建议你自己在草稿纸上画一个 1-2-3-4-5 的链表跟着走一遍。第一轮开始时prev 是 dummyfirst 是1second 是2third 是3。执行完交换后链表变成 dummy-2-1-3-4-5prev 移动到1。第二轮开始时first 取 prev.next也就是3second 是4third 是5。交换后变成 dummy-2-1-4-3-5prev 移动到3。第三轮开始时prev.next 是5prev.next.next 是 None循环退出。最后返回 dummy.next也就是节点2。整个过程清晰且可控没有任何一个节点被遗漏或重复。2.4 循环终止条件与奇数长度链表的处理循环条件写成 while prev.next and prev.next.next这个双条件新手很容易写错成只判断一个。为什么需要两个条件prev.next 存在说明还有至少一个节点可以当 firstprev.next.next 存在说明 first 后面还有第二个节点可以交换。如果链表本身是空的prev.next 就是 None访问 prev.next.next 会直接空指针。如果链表只有一个节点prev.next 存在但 prev.next.next 是 None也不该进入循环。奇数长度链表不受影响的原理也跟着清楚了以5个节点为例最后一轮 prev 在节点3的位置prev.next 指向55.next 是 None所以 while 判定失败节点5保持原样。这正好对应第1节里那张边界表里的情况。循环条件里的每个判断都能在边界表中找到对应场景这是我认为迭代方案最舒服的地方——边界和逻辑是闭环的。3. 递归方案把后半段看成规模更小的同一个问题3.1 先定义递归函数的语义返回新头迭代方案直观但很多面试官还会追问“你能写递归吗”。这时候如果你愣住前面留下的好印象就打折了。递归方案的关键不是背诵代码而是先想清楚一个定义swapPairs(head) 这个函数返回的到底是什么。我的定义是swapPairs(head) 返回“以 head 为头结点的这一段链表经过两两交换后新的头结点”。为什么要强调这个定义因为递归公式里的所有连接都依赖这个返回值。如果 head 为空或者 head 后面没有节点那么这一小段链表根本不需要交换新头还是 head 自己。于是递归的终止条件也顺理成章地出来了。如果你把递归函数想象成一个黑盒调用它就可以得到一个已经交换完毕的新的子链表头那么整个递归写起来就是用这个黑盒拼接外面的两个节点逻辑会清晰得多。很多人递归学不会是因为总想展开完整调用栈去理解每一层其实用一个“信任子问题成立”的心态反而更容易写对。3.2 递归公式推导从head往后拆假设现在传入的链表长这样head-second-rest其中 rest 指的是 second.next 以及之后的所有节点。我们的目标是让 second 跑到 head 前面head 接在 second 后面而 rest 部分作为一个规模更小的子问题交给 swapPairs 去处理。公式可以拆成三步先记录 second head.nexthead.next swapPairs(second.next)这句话的意思是先把 rest 部分两两交换好然后把结果接到 head 后面second.next head让 second 指向 head完成这对节点的交换返回 second因为此时 second 是新的头部。写成代码是这样def swapPairs(head): if not head or not head.next: return head second head.next head.next swapPairs(second.next) second.next head return second注意第2步和第3步的顺序也有讲究。如果先把第二行改成 second.next head那么 second.next 就不再指向 rest 了后面再调用 swapPairs(second.next) 时传进去的就是 head 自己整个递归立刻变成死循环或错误结果。这正是递归版最容易踩的坑先处理子问题再动当前层的 next顺序不能反。3.3 递归终止条件递归终止条件就一句话if not head or not head.next: return head。两个判断缺一不可。缺了 not head空链表进来后访问 head.next 会报空指针缺了 not head.next单节点链表会一直递归下去。实际做题时可以这样记终止条件本质就是“这一段没有可交换的一对节点”和迭代版的双条件 while 是一一对应的。递归版我建议你至少手推一遍 1-2-3-4swapPairs(1) 派生出 swapPairs(3)swapPairs(3) 派生 swapPairs(空)返回空。然后 swapPairs(3) 内部完成 3 和 4 的交换返回4作为新头。回到 swapPairs(1)此时 head.next 被接上节点4second 是2最终 2-1-4-3返回2。推过这一遍之后你会对“返回新头”这四个字有更深的体会。3.4 递归的空间开销为什么面试常要求再写迭代版迭代版的空间复杂度是 O(1)递归版则不然。每次递归调用都会在系统调用栈里压一层链表 n 个节点递归深度大约是 n/2所以空间复杂度是 O(n)。当链表很长的时候递归版存在调用栈溢出的风险。这也是面试官经常在你写递归版之后追问迭代版的原因他们想知道你是否清楚递归在空间上的代价。我的建议是两种写法都要会先讲递归体现思路的清晰再补迭代版展示对空间开销的控制。回答“递归版空间 O(n)迭代版 O(1)工程上长链表优先选迭代”之类的话面试观感会好很多。4. 实测中翻车率最高的几种写法断链顺序、环引用与死循环4.1 一个会形成自环的错误交换顺序我在给 A 同学讲这道题时他写过一段让我印象深刻的错误代码。那段代码的核心是这三步# 错误写法会形成自环 prev.next second second.next first first.next second.next # 这里 second.next 已经是 first 了第一行让 dummy 指向2第二行让2指向1第三行本来是想让1指向原来的后继3但问题在于 second.next 已经被第二行改掉了。所以 first.next second.next 变成了 first.next first链表在节点1处形成了自环。从外部看链表变成了 dummy-2-1-1-1...输出结果完全错误而且遍历还可能进入死循环。这类错误的根源就是我在2.2节强调的“保存后继原则”。正确的做法是提前把 third 存在变量里或者调整代码顺序让 first.next third 在 second.next first 之前完成。链表题的很多崩溃现场起因都不是逻辑复杂而是在一行之内同时引用了同一个指针的“旧值”和“新值”。4.2 忘记更新prev导致的死循环另一个高频错误是交换动作写对了但忘记更新 prev。有人觉得既然 swap 过程中我们已经通过 prev.next second 改变了链路那下一轮循环自然能找到下一个节点为什么还要手动 prev first原因是循环条件的判断对象是 prev.next如果 prev 一直停在 dummy那么不管循环体内部怎么交换下一轮进来时 prev.next 永远指向2永远都在交换1和2这一对。实际表现就是程序陷入死循环输出结果永远只有一组交换后面的节点完全没被处理。更新 prev 是让循环“前进”的关键一步迭代版里 prev 每轮必须移动到当前这组节点的 second 位置上也就是交换后位于后面的 first。你可以把 prev 理解成“上一组交换完成后的最后一个节点”它既是下一组的起步点也是整个链表不断向前的锚点。4.3 本地自测最小工具链打印函数与用例集刷链表题如果不打印链表调试体验会非常痛苦。我建议在本地环境里准备一个最简工具集。首先是构建链表的函数其次是打印链表的函数这两个函数加起来不到二十行能解决绝大多数链表题的验证需求。def build_list(vals): dummy ListNode(0) cur dummy for v in vals: cur.next ListNode(v) cur cur.next return dummy.next def print_list(head): vals [] while head: vals.append(str(head.val)) head head.next print( - .join(vals))测试时直接把第1.3节那张边界表的用例跑一遍for arr in [[], [1], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5]]: result swapPairs(build_list(arr)) print_list(result)对比输出结果空链表不打印任何内容单节点打印1双节点打印2-1三节点打印2-1-3四节点打印2-1-4-3五节点打印2-1-4-3-5。只要有一处结果不一致把当前节点和 prev 的值打印出来基本就能定位是哪一步出了问题。4.4 白板题的自检节奏画箭头、走样例、查空指针面试场景和本地调试不同没有编译器帮你跑测试。我的自检习惯是三个节奏画箭头、走样例、查空指针。画箭头是第一步。在写代码前把 dummy、prev、first、second、third 五个节点的连接关系画出来每改一条 next 就画一条新箭头。很多“为什么先保存 third”的疑惑画着画着自己就明白了。走样例是第二步重点走两个用例4个节点和5个节点的链表。4个节点看完整交换5个节点看奇数尾部如何处理。每走完一轮就标注当前位置 prev 指向谁确保循环在前进。查空指针是第三步逐行看代码里出现的每个 next 访问问自己“这一步有没有可能 next 是 None”。特别是循环条件、递归终止条件这两处是空指针错误的高发地带。这三步做完绝大多数提交错误都能提前拦截住。链表题本身就是一种“手脑协同”的题型画图的时间永远不算浪费。5. 从两两交换延伸出去链表的断链-重连核心思维5.1 两两交换的本质是区间重排刷完这道题后我最大的收获不是会写 swapPairs而是看穿了这类题的通法。两两交换本质上可以理解成“对链表上长度为2的小区间做一次反转”。两个节点交换无非是让原来的第二个节点跑到前面原来的第一个节点跑到后面同时把前后两端的连接重新接好。一旦用这种“区间重排”的视角看问题你就会发现需要关注的接触点其实是四个区间前一个节点、区间内第一个节点、区间内第二个节点、区间后第一个节点。在具体代码里这四个点分别对应 prev、first、second、third。很多教程只教你记住 prev、cur、next 三个指针但真正遇到复杂一点的链表操作时就会断链原因恰恰是漏了区间后第一个节点这个“锚点”。两两交换为什么相对简单因为区间大小只有2即使漏保存 third某些写法还能靠执行顺序歪打正着但一旦区间变大不保存后继几乎必然翻车。5.2 延伸题k个一组翻转两两交换其实是“k个一组翻转链表”在 k2 时的特例。k个一组翻转的完整思路是这样的先从头开始数出 k 个节点如果不够 k 个就保持原样返回如果够 k 个就把这 k 个节点内部的连接关系整体反转然后接到外部链表上。这个时候区间前一个节点和区间后第一个节点的保存就显得尤其重要因为反转完内部之后你必须知道这一段应该接在谁后面。从刷题路线来看我建议在完成两两交换之后紧接着去练 k个一组翻转。你会发现它的主循环里不仅有类似的三指针操作还要额外处理区间长度判断相当于把两两交换的所有难点放大了一遍。练会之后回头再看两两交换那种“杀鸡用牛刀”的从容感会特别舒服。5.3 延伸题部分区间反转与反转链表还有一个延伸方向是“反转链表的一部分”比如反转从第 m 个节点到第 n 个节点的区间。这道题同样需要记录区间前一个节点 leftPrev 和区间后第一个节点 rightNext然后对区间内部执行反转。对比两两交换可以发现反转区间内部时核心操作依然是“保存后继、修改 next、向前推进”这个循环不变式。再往基础看最经典的单链表反转也是一样的套路每次把当前节点的 next 指向前驱但在修改之前必须先保存原来的 next否则链表就断了。所以这些题本质上共用同一个心智模型你手里的指针就是你在链表里的“抓手”每移动一步都要确保下一个抓手还在手里。两两交换是这个模型里最小、最好上手的训练场。5.4 链表类题目的复习顺序与面试加分点如果你刚开始系统刷链表题我建议按下面这个顺序来练环形链表、相交链表理解快慢指针和引用相等。反转链表理解最基本的指针翻转。两两交换链表中的节点理解两个节点的区间重排。k个一组翻转链表综合运用区间长度判断和指针重连。这套顺序的难度是平滑上升的每一道题的坑都会在下一道题里以更复杂的形式出现。面试时如果能主动讲清楚“这里之所以保存 third是因为 second 的 next 马上就要被改写不改写就拿不到后续链表了”面试官通常会很满意。这句话比闷头写对十行代码更能证明你真的理解链表操作的本质。最后说一点我自己的练习体会。我刚开始刷这道题时完全靠背代码第二周再写还是卡住。后来我在电子笔记里为这道题补了三页批注从“为什么先保存 third”到“为什么循环要双条件”每踩一个坑就补一段。三刷之后才彻底醒悟链表操作的底线从来不是记步骤而是在改任何一条 next 之前先把下一步要走的路记住。把这个原则刻进脑子里两两交换、k个一组翻转、区间反转全部都会变得顺理成章。
阅读完成 · 觉得有帮助？
