刷 LeetCode 的人应该都有这种体会链表题看着简单一写就乱。尤其是遇到那种既要找中点、又要反转、还要合并的题目脑子里的指针一多当场就绕进去。今天要拆的这道LeetCode 143 题 Reorder List重排链表正是把链表三大基本功一次性全考完的典型代表也是热门 100 题里出镜率相当高的一道。与其说它是一道题不如说它是一张链表操作的自检清单快慢指针能不能一次写对、反转链表是不是肌肉记忆、断链和拼接有没有留死角全在这道题里暴露无遗。这篇文章不是为了让你背答案而是想从底层把每一步为什么要这么做讲清楚顺便把我在实际刷题和面试复盘里踩过的坑都倒出来无论你是刚接触链表的初学者还是准备春招秋招想快速过一遍高频题的老手都能从里面拿到点能直接用的东西。1. 拿到 143 题先别急着写代码题目本质与整体拆解1.1 题目到底在做什么不绕弯子先把题面讲清楚。给定一个单链表假设是L0 → L1 → … → Ln-1 → Ln要求把它原地重排成L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …。说白了就是一头一尾交替取节点重新编织出一条链表。注意题目明确要求“原地”也就是说你不能简单地把节点值存到数组里然后换顺序必须真的去调整节点的next指针。举个例子链表1 → 2 → 3 → 4 → 5重排后应该是1 → 5 → 2 → 4 → 3。再看一个偶数长度的1 → 2 → 3 → 4 → 5 → 6重排后是1 → 6 → 2 → 5 → 3 → 4。从这个结果能直接看出一个规律前面半段节点的相对顺序没变变的是后半段的节点被反向穿插进来了。这个观察非常重要因为所有高效解法本质上都是在实现这个“后半段逆序 交替插入”的过程。很多初学者看到这道题的第一反应是直接模拟从头部取一个再从尾部取一个。但单链表根本没法从尾往前访问你总不能用 O(n) 的时间去遍历一遍找尾节点吧那样整体复杂度直接变成 O(n²)数据一大就超时。所以我们要做的第一件事就是把“看起来很直观”的暴力思路扔掉切换到“拆解问题”的思维模式。1.2 三种思路的取舍为什么三步法是面试官最想看到的既然直接模拟行不通那就把它拆开。重排的结果本质上是“前半段 反转后的后半段”交叉合并。顺着这个思路往下走大概有三条路线第一条最简单遍历一遍链表把节点依序放进一个 ArrayList 或数组里然后用双指针从两端交替取节点重建链表。这个方法我在初期刷题时也用过优点是非常直观、几乎不可能出错缺点是额外空间 O(n)。面试时如果你只给出这个解法面试官大概率会追问一句“能不能把空间压到 O(1)”第二条是用递归或栈。递归天然具备回溯的能力可以先递归到链表尾部再回溯过程中完成重排栈呢就是把后半段节点压栈弹出时和前半段交替连接。这两个办法和数组法本质差不多空间复杂度也是 O(n)递归还会有很深的调用栈风险实在不算优雅。第三条就是标准的三步法也是我推荐你重点掌握的用快慢指针找到链表的中点。把中点之后的链表段反转。把两条链表交错合并回一条。为什么这条路线是面试官最想看到的因为它把一道“看起来复杂”的重排题分解成了三个在 LeetCode 上各自成题的基础考点找中点是876. Middle of the Linked List反转链表是206. Reverse Linked List合并链表是21. Merge Two Sorted Lists的变体。你等于用一道题同时复习了三个高频模板而且每一步的空间复杂度都是 O(1)整体保持原地操作。面试的时候你如果能主动说出“这道题其实是在考三个基本功的组合”就已经赢了一半因为这说明你不是在背题而是在理解题目结构。1.3 三步法的核心是怎么炼成的我刷链表题多年最大的感触是链表问题永远不要“记住一个答案”而要“记住一套决策流程”。比如看到 143你脑子里首先应该跳出“能不能拆成已经会做的子问题”这个念头。拆完之后你会发现找中点、反转、合并每一块单独拿出来都是闭着眼睛能写的代码那组合起来就不该慌。这套拆解能力不是天生的是练出来的。我在带新人刷题时经常说如果你连 206 反转链表都要想半天那就先别碰 143。先把单点技能练到肌肉记忆再来做组合题。下面这章我按顺序把三步里最容易出问题的细节逐个拆开讲每一点都是我实际写代码时反复栽过跟头的地方。2. 核心细节拆解每个步骤的“坑”都藏在这里2.1 快慢指针找中点一个.next的差别决定生死第一步是找中点。快慢指针的基本逻辑大家应该都听过slow每次走一步fast每次走两步当fast走到链表末尾时slow正好在中间位置。但这里有一个说起来简单、写起来容易翻车的细节fast的初始值到底该设为head还是head.next我先把两种写法摆出来。写法 AListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }写法 BListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }这两种写法在有些链表长度下结果一样在有些长度下结果不一样。以链表1 → 2 → 3 → 4 → 5为例写法 A 循环结束时slow停在中点3写法 B 因为fast一开始就多走了半拍循环结束后slow同样停在3。但如果链表是偶数长度1 → 2 → 3 → 4 → 5 → 6写法 A 的slow停在4写法 B 的slow停在3。这个差异非常关键因为它直接决定了后半段从哪里开始。你仔细看 143 的要求偶数长度时重排后最后两个节点是3 → 4也就是说前半段应该是1 → 2 → 3后半段应该是4 → 5 → 6反转后半段后得到6 → 5 → 4再和前半段交替拼成1 → 6 → 2 → 5 → 3 → 4。如果用写法 Aslow停在4那前半段会变成1 → 2 → 3 → 4后半段是5 → 6合并出来是1 → 6 → 2 → 5 → 3 → 4结果居然也正确。为什么因为多出来的4实际上成了最终的尾节点两个段的分法不同但殊途同归。那到底选哪种我的建议是用写法 Bfast head.next。理由有两条。第一从语义上说对于奇数长度它能保证slow停在整个链表真正的中间节点对于偶数长度它能保证slow停在前半段的末尾这样slow.next就是后半段的第一个节点划分更干净。第二也是更实际的理由写法 B 在断链后前半段天然不会把后半段的第一个节点包含进来边界更好理解。当然你完全可以用写法 A只要心里清楚它的中点偏移规律代码没问题也 OK。但面试时为了少花时间解释边界直接用写法 B 更省事。这里还要提醒一点循环条件fast ! null fast.next ! null顺序千万别写反。如果你先判断fast.next而此时的fast已经是null直接空指针异常。Java 里有短路特性把fast ! null放前面是安全的。2.2 反转后半链表迭代三指针必须养成的肌肉记忆第二步是反转后半段。反转链表的迭代写法网上模板一堆但真正能手写出且不改错的并不多。我见过太多人写这种反转ListNode pre null; ListNode cur second; while (cur ! null) { ListNode next cur.next; cur.next pre; pre cur; cur next; }这段代码我建议你闭着眼睛都能敲出来因为它是很多链表题的基石。这里面唯一容易出错的点是cur.next pre和pre cur这两行到底谁先谁后。很多人一紧张就把赋值顺序写反结果链表直接断掉。我的记忆方法是先把cur.next原来的指向存进临时变量然后再动cur.next的指向让它反转指向前驱最后把pre和cur都往后平移。整个过程相当于你在一列人里逐个让人转过身来面对前一个人转完一个往前走一个。在 143 题里反转的对象不是整个链表而是从slow.next开始的半段。这里有个极其容易踩的坑反转之前先把slow.next置为null。如果不做这一步前半段和后半段之间还连着后面合并的时候就全乱了甚至可能出现循环引用导致程序死循环。断链这一步我把它视为整个 143 题里最不该省的操作。2.3 合并两个链表交叉编织谁先谁后有讲究第三步是合并。这时你有两条链表前半段first头节点是head和反转后的后半段second头节点是反转后的新头。合并的目标不是像 21 题那样按值合并而是交叉穿插先取一个first的节点再取一个second的节点循环往复直到second被取完。合并的代码有很多种等价写法我推荐下面这种ListNode first head; ListNode second secondHead; while (second ! null) { ListNode tmp1 first.next; ListNode tmp2 second.next; first.next second; second.next tmp1; first tmp1; second tmp2; }这个循环的终止条件为什么是second ! null因为后半段在长度上不会超过前半段快慢指针的分法保证了这一点所以当second取完时first可能还剩最后一个节点不需要再处理它直接作为链表的尾节点即可。这正好对应了奇数长度时最后那个中间节点不需要被穿插的情况。还有一点需要说明在循环体里必须先保存tmp1 first.next和tmp2 second.next再做指针调整。很多人会忽略保存first.next结果把链表的前半段顺序带偏。其实你只要记住一个原则凡是节点的next要被改写先把它原来的下一个节点存下来就不会错。这可以说是链表操作的通用第一守则。3. 完整实操代码实现与逐行讲解3.1 Java 与 Python 的完整可运行代码理论说得再多不如直接跑一段代码。这里给出我本地验证过的 Java 版本class Solution { public void reorderList(ListNode head) { if (head null || head.next null) { return; } // 1. 快慢指针找中点fast 从 head.next 出发 ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 此时 slow 是前半段的尾节点second 是后半段的头节点 ListNode second slow.next; slow.next null; // 关键断链 // 2. 反转后半段 ListNode prev null; ListNode curr second; while (curr ! null) { ListNode nextTemp curr.next; curr.next prev; prev curr; curr nextTemp; } ListNode secondHead prev; // 3. 交错合并两条链表 ListNode first head; ListNode secondList secondHead; while (secondList ! null) { ListNode tmp1 first.next; ListNode tmp2 secondList.next; first.next secondList; secondList.next tmp1; first tmp1; secondList tmp2; } } }Python 版本同样简洁class Solution: def reorderList(self, head: ListNode) - None: if not head or not head.next: return slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next second slow.next slow.next None prev, curr None, second while curr: next_temp curr.next curr.next prev prev, curr curr, next_temp first, second head, prev while second: tmp1 first.next tmp2 second.next first.next second second.next tmp1 first, second tmp1, tmp2我已经用1 → 2 → 3 → 4 → 5和1 → 2 → 3 → 4 → 5 → 6两个典型长度都跑过输出结果分别是1 → 5 → 2 → 4 → 3和1 → 6 → 2 → 5 → 3 → 4完全符合预期。如果你在自己的 IDE 里跑记得带入标准链表定义结构比如 Java 里需要ListNode这个内部类Python 则需要 LeetCode 环境已经替你定义好ListNode。3.2 用一个具体例子跟着代码走一遍光贴代码不演示过程等于没讲。我们拿1 → 2 → 3 → 4 → 5这个最容易被大家用来测试的链表从头到尾捋一遍指针状态。初始状态head指向节点 1slow 1fast 2。进入快慢指针循环第一次循环fast 2非空fast.next 3非空执行slow slow.nextslow变成 2fast fast.next.nextfast变成 4。第二次循环fast 4非空fast.next 5非空执行slow slow.nextslow变成 3fast fast.next.nextfast变成null。第三次判断fast为空退出循环。此时slow停在节点 3。我们令second slow.next也就是节点 4。然后执行slow.next null链表从中间断开变成两条前半段1 → 2 → 3后半段4 → 5。注意这里如果不把3.next置空后面合并时就会出现段和段之间的“藕断丝连”。反转后半段curr从节点 4 开始第一次循环后局部变成null ← 4也就是 4 的next指向prev初始为nullprev变成 4curr变成 5。第二次循环后5 的next指向 4prev变成 5curr变成null。反转完成后后半段的头节点secondHead 5链表结构是5 → 4。合并阶段first指向 1secondList指向 5。第一轮tmp1 first.next即节点 2tmp2 secondList.next即节点 4。执行first.next secondList节点 1 指向 5执行secondList.next tmp1节点 5 指向 2。此时链表片段为1 → 5 → 2并且2后面还连着3。移动指针first tmp1也就是 2secondList tmp2也就是 4。第二轮tmp1 first.next即节点 3tmp2 secondList.next此时 4 的next是null所以tmp2 null。执行first.next secondList节点 2 指向 4执行secondList.next tmp1节点 4 指向 3。移动指针后secondList null循环结束。最终链表为1 → 5 → 2 → 4 → 3。完美符合答案。你发现没有合并阶段里最妙的是节点 3 从头到尾都没被单独操作过它只是被第二轮的4.next指向了一下就自然成为尾节点。这就是为什么second ! null作为循环条件的合理性后半段全部被穿插完前半段剩下的节点自动续在尾部。3.3 复杂度与空间优化说明时间上找中点遍历了一次链表反转后半段遍历了后半段合并又遍历了一次整体是 O(n)。因为每一步都只是常数次操作所以常数系数也不大。空间上全程只用到了若干个临时指针变量slow、fast、prev、curr、tmp1、tmp2等没有使用额外的容器空间复杂度 O(1)。很多人会问这种优化真的有必要吗我个人的看法是LeetCode 的判题系统可能不会因为你用了一个 ArrayList 就挂你但面试官绝对会追问。链表类问题考的就是你能不能在不借用额外空间的情况下只靠调整指针完成任务。你要是能在白板上把 O(n) 空间解法优化到 O(1)这本身就是加分项。而且把空间复杂度降下来之后你会发现对指针的理解明显更深了一层后面做25. Reverse Nodes in k-Group、24. Swap Nodes in Pairs这类题会顺手很多。4. 常见问题与排查技巧实录4.1 你大概率会遇到的三个 Bug第一个 Bug空指针异常。这通常发生在你的快慢指针循环条件写反了或者链表本身就是空链表/单节点链表时。我一般会在方法开头做一次防御if (head null || head.next null) { return; }这行代码看着简单但很多人因为没加测试用例一跑就崩。面试时如果忘了被面试官提醒就很尴尬。第二个 Bug合并后链表成环。这是我见过最多的问题。根本原因是断链没做好或者临时指针保存错了位置。比如合并第一轮里没保存tmp1 first.next直接把first.next改成了secondList那原始的下一个节点信息就丢了链表后段就会错乱。另一种成环方式是slow.next没有置为null后半段反转后反转链表的尾节点还指着前半段的某个节点合并时整个链表变成一个环程序陷入死循环。排查方法也很简单在代码里临时输出每一步next指针或者直接在测试用例上手动推演一次。第三个 Bug偶数长度链表的结果不对。如果你发现1 → 2 → 3 → 4 → 5 → 6被重排成了1 → 6 → 2 → 5 → 3 → 4以外的其他样子多半是快慢指针的中点定位偏了。比如用fast head写法的同学如果后续处理没适配中点偏移合并时会把后半段多包含一个或少包含一个节点。解决办法就是回到 2.1 节确认自己选的写法对应的中点规律然后统一用一套逻辑。4.2 边界测试用例速查表刷题不能只看标准用例边界用例才是真正检验代码质量的地方。我把 143 题常用的边界测试情况整理了一下你可以直接照着在自己本地跑一跑测试链表期望输出检测重点nullnull空链表是否安全返回11单节点链表是否安全返回1 → 21 → 2双节点链表不应出错1 → 2 → 31 → 3 → 2奇数长度、三段结构1 → 2 → 3 → 41 → 4 → 2 → 3偶数长度、四段结构1 → 2 → 3 → 4 → 51 → 5 → 2 → 4 → 3教材级标准用例大量节点如 10000 个符合规律确认不是 O(n²) 且不超时我特别建议你跑一下双节点的情况。很多人的代码在空链表、单节点上做了防御却忽略了双节点已经需要走完整三步。实际上双节点时快慢指针找中点后second是第二个节点反转后不变合并后结果自然还是1 → 2。如果这段代码没写对说明逻辑里可能有隐含条件没覆盖到。4.3 测试驱动从“功能正确”到“无懈可击”我自己的习惯是写完代码先跑标准示例再跑边界用例最后再随机生成一个中等长度的链表用数组模拟答案对比验证。LeetCode 的 Playground 可以直接调试很方便。如果你是在本地 IDE 做题可以写个辅助函数把链表转成数组再对比重排前后的数组是否符合预期。这一步虽然慢但能帮你建立“代码不靠猜靠验证”的刷题习惯。这里分享一个小工具函数我用得特别频繁把链表打印成数组public ListInteger toList(ListNode head) { ListInteger res new ArrayList(); while (head ! null) { res.add(head.val); head head.next; } return res; }每次测完 143我都习惯性地打印一遍重排后的链表看到输出是[1, 5, 2, 4, 3]这种整齐序列心里才踏实。链表题的麻烦之处在于你不打印就看不到中间状态调试时全靠脑补所以千万别嫌打印麻烦。5. 横向扩展一道题带出一串题5.1 周赛 430 与热门 100 题链表重排的变形考法聊到这儿你应该已经掌握 143 题的核心解法了。但刷题不能只盯着一道题得学会从一道题看到一片题。如果你去翻 LeetCode 的热门 100 题和每周周赛会发现“找到中点 反转 合并”这套组合被反复包装成各种新题。比如234. Palindrome Linked List判断回文链表思路就是找到中点、反转后半段、再逐节点比较再比如一些关于链表成对交换节点、间隔取点的变体本质上都是对基础操作的不同排列组合。我常跟人说周赛题目虽然包装得花里胡哨但剥开外壳内核永远是那些经典套路。比如上周的周赛 430 就有不少题目本质上在考基础数据结构的灵活运用如果你平时把 143 这种组合题吃透了赛场上看到类似结构就能很快反应过来该往哪个方向拆。链表题尤其如此它不像动态规划需要庞大的题量积累只要把指针操作练扎实很多题就是“瞬间看透”。5.2 073 爱吃香蕉的狒狒不同套路但同样高频的二分答案题说句题外话但又是必要的题外话。最近讨论度很高的 LeetCode 题目里除了这类链表重排还有一道“073 爱吃香蕉的狒狒”——也就是很多人提到的 Koko Eating Bananas 那道题。它讲的是一个叫 Koko 的狒狒要吃香蕉每小时能吃一堆中的若干根要求在限定时间内吃完问你最小的吃速是多少。题目模型一点都不复杂本质上是对“速度”这个变量做二分查找每次判断“这个速度能否在 H 小时内吃完”属于非常典型的二分答案题。我为什么在 143 题的总结里专门提这一道因为它代表的是另一类高频面试题不考复杂的数据结构但考你能否看出“单调性 二分”的套路。链表重排考验的是指针操作的基本功二分答案考验的是算法思维的敏捷度。这两类题一硬一软恰好覆盖了面试中最常被考察的两个维度。如果你把 143 题和 073 题都吃透了等于在“结构操作”和“数值搜索”两条线上都有了拿得出手的底牌。5.3 刷题节奏建议组合题要拆着练最后聊点刷题方法论。我见过太多人把 143 题背下来再遇到一道“同时考两个知识点”的题就懵了。问题出在练习方式上。我的建议是遇到组合题先主动把它拆成几个子问题然后去把对应的基础题单独刷熟。比如 143 题可以拆成Middle of the Linked List练快慢指针Reverse Linked List练习反转指针Merge Two Sorted Lists练习链表合并时指针交替移动。这三道题每道都能在 15 分钟内写完连续刷三天保证你的指针感有明显提升。等你回头看 143 题会发现它不再是一道“吓人”的难题而是三个你已经掌握的模板文件的组合写起来行云流水。我个人在实际刷题中最受益的一个习惯是每次做完一道组合题就在笔记里写一句话总结“这道题是由哪些基础题拼起来的”。积累一段时间后再回看你会发现自己面对新题时的拆解速度变快了不是因为你见过所有题而是因为你见过的“零件”足够多。143 题就是这样一个标准的“零件箱”题目吃透它对你后续刷很多链表题的帮助远超它本身的分值。
LeetCode 143 重排链表：快慢指针、反转与合并的链表三步法全解
刷 LeetCode 的人应该都有这种体会链表题看着简单一写就乱。尤其是遇到那种既要找中点、又要反转、还要合并的题目脑子里的指针一多当场就绕进去。今天要拆的这道LeetCode 143 题 Reorder List重排链表正是把链表三大基本功一次性全考完的典型代表也是热门 100 题里出镜率相当高的一道。与其说它是一道题不如说它是一张链表操作的自检清单快慢指针能不能一次写对、反转链表是不是肌肉记忆、断链和拼接有没有留死角全在这道题里暴露无遗。这篇文章不是为了让你背答案而是想从底层把每一步为什么要这么做讲清楚顺便把我在实际刷题和面试复盘里踩过的坑都倒出来无论你是刚接触链表的初学者还是准备春招秋招想快速过一遍高频题的老手都能从里面拿到点能直接用的东西。1. 拿到 143 题先别急着写代码题目本质与整体拆解1.1 题目到底在做什么不绕弯子先把题面讲清楚。给定一个单链表假设是L0 → L1 → … → Ln-1 → Ln要求把它原地重排成L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …。说白了就是一头一尾交替取节点重新编织出一条链表。注意题目明确要求“原地”也就是说你不能简单地把节点值存到数组里然后换顺序必须真的去调整节点的next指针。举个例子链表1 → 2 → 3 → 4 → 5重排后应该是1 → 5 → 2 → 4 → 3。再看一个偶数长度的1 → 2 → 3 → 4 → 5 → 6重排后是1 → 6 → 2 → 5 → 3 → 4。从这个结果能直接看出一个规律前面半段节点的相对顺序没变变的是后半段的节点被反向穿插进来了。这个观察非常重要因为所有高效解法本质上都是在实现这个“后半段逆序 交替插入”的过程。很多初学者看到这道题的第一反应是直接模拟从头部取一个再从尾部取一个。但单链表根本没法从尾往前访问你总不能用 O(n) 的时间去遍历一遍找尾节点吧那样整体复杂度直接变成 O(n²)数据一大就超时。所以我们要做的第一件事就是把“看起来很直观”的暴力思路扔掉切换到“拆解问题”的思维模式。1.2 三种思路的取舍为什么三步法是面试官最想看到的既然直接模拟行不通那就把它拆开。重排的结果本质上是“前半段 反转后的后半段”交叉合并。顺着这个思路往下走大概有三条路线第一条最简单遍历一遍链表把节点依序放进一个 ArrayList 或数组里然后用双指针从两端交替取节点重建链表。这个方法我在初期刷题时也用过优点是非常直观、几乎不可能出错缺点是额外空间 O(n)。面试时如果你只给出这个解法面试官大概率会追问一句“能不能把空间压到 O(1)”第二条是用递归或栈。递归天然具备回溯的能力可以先递归到链表尾部再回溯过程中完成重排栈呢就是把后半段节点压栈弹出时和前半段交替连接。这两个办法和数组法本质差不多空间复杂度也是 O(n)递归还会有很深的调用栈风险实在不算优雅。第三条就是标准的三步法也是我推荐你重点掌握的用快慢指针找到链表的中点。把中点之后的链表段反转。把两条链表交错合并回一条。为什么这条路线是面试官最想看到的因为它把一道“看起来复杂”的重排题分解成了三个在 LeetCode 上各自成题的基础考点找中点是876. Middle of the Linked List反转链表是206. Reverse Linked List合并链表是21. Merge Two Sorted Lists的变体。你等于用一道题同时复习了三个高频模板而且每一步的空间复杂度都是 O(1)整体保持原地操作。面试的时候你如果能主动说出“这道题其实是在考三个基本功的组合”就已经赢了一半因为这说明你不是在背题而是在理解题目结构。1.3 三步法的核心是怎么炼成的我刷链表题多年最大的感触是链表问题永远不要“记住一个答案”而要“记住一套决策流程”。比如看到 143你脑子里首先应该跳出“能不能拆成已经会做的子问题”这个念头。拆完之后你会发现找中点、反转、合并每一块单独拿出来都是闭着眼睛能写的代码那组合起来就不该慌。这套拆解能力不是天生的是练出来的。我在带新人刷题时经常说如果你连 206 反转链表都要想半天那就先别碰 143。先把单点技能练到肌肉记忆再来做组合题。下面这章我按顺序把三步里最容易出问题的细节逐个拆开讲每一点都是我实际写代码时反复栽过跟头的地方。2. 核心细节拆解每个步骤的“坑”都藏在这里2.1 快慢指针找中点一个.next的差别决定生死第一步是找中点。快慢指针的基本逻辑大家应该都听过slow每次走一步fast每次走两步当fast走到链表末尾时slow正好在中间位置。但这里有一个说起来简单、写起来容易翻车的细节fast的初始值到底该设为head还是head.next我先把两种写法摆出来。写法 AListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }写法 BListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; }这两种写法在有些链表长度下结果一样在有些长度下结果不一样。以链表1 → 2 → 3 → 4 → 5为例写法 A 循环结束时slow停在中点3写法 B 因为fast一开始就多走了半拍循环结束后slow同样停在3。但如果链表是偶数长度1 → 2 → 3 → 4 → 5 → 6写法 A 的slow停在4写法 B 的slow停在3。这个差异非常关键因为它直接决定了后半段从哪里开始。你仔细看 143 的要求偶数长度时重排后最后两个节点是3 → 4也就是说前半段应该是1 → 2 → 3后半段应该是4 → 5 → 6反转后半段后得到6 → 5 → 4再和前半段交替拼成1 → 6 → 2 → 5 → 3 → 4。如果用写法 Aslow停在4那前半段会变成1 → 2 → 3 → 4后半段是5 → 6合并出来是1 → 6 → 2 → 5 → 3 → 4结果居然也正确。为什么因为多出来的4实际上成了最终的尾节点两个段的分法不同但殊途同归。那到底选哪种我的建议是用写法 Bfast head.next。理由有两条。第一从语义上说对于奇数长度它能保证slow停在整个链表真正的中间节点对于偶数长度它能保证slow停在前半段的末尾这样slow.next就是后半段的第一个节点划分更干净。第二也是更实际的理由写法 B 在断链后前半段天然不会把后半段的第一个节点包含进来边界更好理解。当然你完全可以用写法 A只要心里清楚它的中点偏移规律代码没问题也 OK。但面试时为了少花时间解释边界直接用写法 B 更省事。这里还要提醒一点循环条件fast ! null fast.next ! null顺序千万别写反。如果你先判断fast.next而此时的fast已经是null直接空指针异常。Java 里有短路特性把fast ! null放前面是安全的。2.2 反转后半链表迭代三指针必须养成的肌肉记忆第二步是反转后半段。反转链表的迭代写法网上模板一堆但真正能手写出且不改错的并不多。我见过太多人写这种反转ListNode pre null; ListNode cur second; while (cur ! null) { ListNode next cur.next; cur.next pre; pre cur; cur next; }这段代码我建议你闭着眼睛都能敲出来因为它是很多链表题的基石。这里面唯一容易出错的点是cur.next pre和pre cur这两行到底谁先谁后。很多人一紧张就把赋值顺序写反结果链表直接断掉。我的记忆方法是先把cur.next原来的指向存进临时变量然后再动cur.next的指向让它反转指向前驱最后把pre和cur都往后平移。整个过程相当于你在一列人里逐个让人转过身来面对前一个人转完一个往前走一个。在 143 题里反转的对象不是整个链表而是从slow.next开始的半段。这里有个极其容易踩的坑反转之前先把slow.next置为null。如果不做这一步前半段和后半段之间还连着后面合并的时候就全乱了甚至可能出现循环引用导致程序死循环。断链这一步我把它视为整个 143 题里最不该省的操作。2.3 合并两个链表交叉编织谁先谁后有讲究第三步是合并。这时你有两条链表前半段first头节点是head和反转后的后半段second头节点是反转后的新头。合并的目标不是像 21 题那样按值合并而是交叉穿插先取一个first的节点再取一个second的节点循环往复直到second被取完。合并的代码有很多种等价写法我推荐下面这种ListNode first head; ListNode second secondHead; while (second ! null) { ListNode tmp1 first.next; ListNode tmp2 second.next; first.next second; second.next tmp1; first tmp1; second tmp2; }这个循环的终止条件为什么是second ! null因为后半段在长度上不会超过前半段快慢指针的分法保证了这一点所以当second取完时first可能还剩最后一个节点不需要再处理它直接作为链表的尾节点即可。这正好对应了奇数长度时最后那个中间节点不需要被穿插的情况。还有一点需要说明在循环体里必须先保存tmp1 first.next和tmp2 second.next再做指针调整。很多人会忽略保存first.next结果把链表的前半段顺序带偏。其实你只要记住一个原则凡是节点的next要被改写先把它原来的下一个节点存下来就不会错。这可以说是链表操作的通用第一守则。3. 完整实操代码实现与逐行讲解3.1 Java 与 Python 的完整可运行代码理论说得再多不如直接跑一段代码。这里给出我本地验证过的 Java 版本class Solution { public void reorderList(ListNode head) { if (head null || head.next null) { return; } // 1. 快慢指针找中点fast 从 head.next 出发 ListNode slow head; ListNode fast head.next; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 此时 slow 是前半段的尾节点second 是后半段的头节点 ListNode second slow.next; slow.next null; // 关键断链 // 2. 反转后半段 ListNode prev null; ListNode curr second; while (curr ! null) { ListNode nextTemp curr.next; curr.next prev; prev curr; curr nextTemp; } ListNode secondHead prev; // 3. 交错合并两条链表 ListNode first head; ListNode secondList secondHead; while (secondList ! null) { ListNode tmp1 first.next; ListNode tmp2 secondList.next; first.next secondList; secondList.next tmp1; first tmp1; secondList tmp2; } } }Python 版本同样简洁class Solution: def reorderList(self, head: ListNode) - None: if not head or not head.next: return slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next second slow.next slow.next None prev, curr None, second while curr: next_temp curr.next curr.next prev prev, curr curr, next_temp first, second head, prev while second: tmp1 first.next tmp2 second.next first.next second second.next tmp1 first, second tmp1, tmp2我已经用1 → 2 → 3 → 4 → 5和1 → 2 → 3 → 4 → 5 → 6两个典型长度都跑过输出结果分别是1 → 5 → 2 → 4 → 3和1 → 6 → 2 → 5 → 3 → 4完全符合预期。如果你在自己的 IDE 里跑记得带入标准链表定义结构比如 Java 里需要ListNode这个内部类Python 则需要 LeetCode 环境已经替你定义好ListNode。3.2 用一个具体例子跟着代码走一遍光贴代码不演示过程等于没讲。我们拿1 → 2 → 3 → 4 → 5这个最容易被大家用来测试的链表从头到尾捋一遍指针状态。初始状态head指向节点 1slow 1fast 2。进入快慢指针循环第一次循环fast 2非空fast.next 3非空执行slow slow.nextslow变成 2fast fast.next.nextfast变成 4。第二次循环fast 4非空fast.next 5非空执行slow slow.nextslow变成 3fast fast.next.nextfast变成null。第三次判断fast为空退出循环。此时slow停在节点 3。我们令second slow.next也就是节点 4。然后执行slow.next null链表从中间断开变成两条前半段1 → 2 → 3后半段4 → 5。注意这里如果不把3.next置空后面合并时就会出现段和段之间的“藕断丝连”。反转后半段curr从节点 4 开始第一次循环后局部变成null ← 4也就是 4 的next指向prev初始为nullprev变成 4curr变成 5。第二次循环后5 的next指向 4prev变成 5curr变成null。反转完成后后半段的头节点secondHead 5链表结构是5 → 4。合并阶段first指向 1secondList指向 5。第一轮tmp1 first.next即节点 2tmp2 secondList.next即节点 4。执行first.next secondList节点 1 指向 5执行secondList.next tmp1节点 5 指向 2。此时链表片段为1 → 5 → 2并且2后面还连着3。移动指针first tmp1也就是 2secondList tmp2也就是 4。第二轮tmp1 first.next即节点 3tmp2 secondList.next此时 4 的next是null所以tmp2 null。执行first.next secondList节点 2 指向 4执行secondList.next tmp1节点 4 指向 3。移动指针后secondList null循环结束。最终链表为1 → 5 → 2 → 4 → 3。完美符合答案。你发现没有合并阶段里最妙的是节点 3 从头到尾都没被单独操作过它只是被第二轮的4.next指向了一下就自然成为尾节点。这就是为什么second ! null作为循环条件的合理性后半段全部被穿插完前半段剩下的节点自动续在尾部。3.3 复杂度与空间优化说明时间上找中点遍历了一次链表反转后半段遍历了后半段合并又遍历了一次整体是 O(n)。因为每一步都只是常数次操作所以常数系数也不大。空间上全程只用到了若干个临时指针变量slow、fast、prev、curr、tmp1、tmp2等没有使用额外的容器空间复杂度 O(1)。很多人会问这种优化真的有必要吗我个人的看法是LeetCode 的判题系统可能不会因为你用了一个 ArrayList 就挂你但面试官绝对会追问。链表类问题考的就是你能不能在不借用额外空间的情况下只靠调整指针完成任务。你要是能在白板上把 O(n) 空间解法优化到 O(1)这本身就是加分项。而且把空间复杂度降下来之后你会发现对指针的理解明显更深了一层后面做25. Reverse Nodes in k-Group、24. Swap Nodes in Pairs这类题会顺手很多。4. 常见问题与排查技巧实录4.1 你大概率会遇到的三个 Bug第一个 Bug空指针异常。这通常发生在你的快慢指针循环条件写反了或者链表本身就是空链表/单节点链表时。我一般会在方法开头做一次防御if (head null || head.next null) { return; }这行代码看着简单但很多人因为没加测试用例一跑就崩。面试时如果忘了被面试官提醒就很尴尬。第二个 Bug合并后链表成环。这是我见过最多的问题。根本原因是断链没做好或者临时指针保存错了位置。比如合并第一轮里没保存tmp1 first.next直接把first.next改成了secondList那原始的下一个节点信息就丢了链表后段就会错乱。另一种成环方式是slow.next没有置为null后半段反转后反转链表的尾节点还指着前半段的某个节点合并时整个链表变成一个环程序陷入死循环。排查方法也很简单在代码里临时输出每一步next指针或者直接在测试用例上手动推演一次。第三个 Bug偶数长度链表的结果不对。如果你发现1 → 2 → 3 → 4 → 5 → 6被重排成了1 → 6 → 2 → 5 → 3 → 4以外的其他样子多半是快慢指针的中点定位偏了。比如用fast head写法的同学如果后续处理没适配中点偏移合并时会把后半段多包含一个或少包含一个节点。解决办法就是回到 2.1 节确认自己选的写法对应的中点规律然后统一用一套逻辑。4.2 边界测试用例速查表刷题不能只看标准用例边界用例才是真正检验代码质量的地方。我把 143 题常用的边界测试情况整理了一下你可以直接照着在自己本地跑一跑测试链表期望输出检测重点nullnull空链表是否安全返回11单节点链表是否安全返回1 → 21 → 2双节点链表不应出错1 → 2 → 31 → 3 → 2奇数长度、三段结构1 → 2 → 3 → 41 → 4 → 2 → 3偶数长度、四段结构1 → 2 → 3 → 4 → 51 → 5 → 2 → 4 → 3教材级标准用例大量节点如 10000 个符合规律确认不是 O(n²) 且不超时我特别建议你跑一下双节点的情况。很多人的代码在空链表、单节点上做了防御却忽略了双节点已经需要走完整三步。实际上双节点时快慢指针找中点后second是第二个节点反转后不变合并后结果自然还是1 → 2。如果这段代码没写对说明逻辑里可能有隐含条件没覆盖到。4.3 测试驱动从“功能正确”到“无懈可击”我自己的习惯是写完代码先跑标准示例再跑边界用例最后再随机生成一个中等长度的链表用数组模拟答案对比验证。LeetCode 的 Playground 可以直接调试很方便。如果你是在本地 IDE 做题可以写个辅助函数把链表转成数组再对比重排前后的数组是否符合预期。这一步虽然慢但能帮你建立“代码不靠猜靠验证”的刷题习惯。这里分享一个小工具函数我用得特别频繁把链表打印成数组public ListInteger toList(ListNode head) { ListInteger res new ArrayList(); while (head ! null) { res.add(head.val); head head.next; } return res; }每次测完 143我都习惯性地打印一遍重排后的链表看到输出是[1, 5, 2, 4, 3]这种整齐序列心里才踏实。链表题的麻烦之处在于你不打印就看不到中间状态调试时全靠脑补所以千万别嫌打印麻烦。5. 横向扩展一道题带出一串题5.1 周赛 430 与热门 100 题链表重排的变形考法聊到这儿你应该已经掌握 143 题的核心解法了。但刷题不能只盯着一道题得学会从一道题看到一片题。如果你去翻 LeetCode 的热门 100 题和每周周赛会发现“找到中点 反转 合并”这套组合被反复包装成各种新题。比如234. Palindrome Linked List判断回文链表思路就是找到中点、反转后半段、再逐节点比较再比如一些关于链表成对交换节点、间隔取点的变体本质上都是对基础操作的不同排列组合。我常跟人说周赛题目虽然包装得花里胡哨但剥开外壳内核永远是那些经典套路。比如上周的周赛 430 就有不少题目本质上在考基础数据结构的灵活运用如果你平时把 143 这种组合题吃透了赛场上看到类似结构就能很快反应过来该往哪个方向拆。链表题尤其如此它不像动态规划需要庞大的题量积累只要把指针操作练扎实很多题就是“瞬间看透”。5.2 073 爱吃香蕉的狒狒不同套路但同样高频的二分答案题说句题外话但又是必要的题外话。最近讨论度很高的 LeetCode 题目里除了这类链表重排还有一道“073 爱吃香蕉的狒狒”——也就是很多人提到的 Koko Eating Bananas 那道题。它讲的是一个叫 Koko 的狒狒要吃香蕉每小时能吃一堆中的若干根要求在限定时间内吃完问你最小的吃速是多少。题目模型一点都不复杂本质上是对“速度”这个变量做二分查找每次判断“这个速度能否在 H 小时内吃完”属于非常典型的二分答案题。我为什么在 143 题的总结里专门提这一道因为它代表的是另一类高频面试题不考复杂的数据结构但考你能否看出“单调性 二分”的套路。链表重排考验的是指针操作的基本功二分答案考验的是算法思维的敏捷度。这两类题一硬一软恰好覆盖了面试中最常被考察的两个维度。如果你把 143 题和 073 题都吃透了等于在“结构操作”和“数值搜索”两条线上都有了拿得出手的底牌。5.3 刷题节奏建议组合题要拆着练最后聊点刷题方法论。我见过太多人把 143 题背下来再遇到一道“同时考两个知识点”的题就懵了。问题出在练习方式上。我的建议是遇到组合题先主动把它拆成几个子问题然后去把对应的基础题单独刷熟。比如 143 题可以拆成Middle of the Linked List练快慢指针Reverse Linked List练习反转指针Merge Two Sorted Lists练习链表合并时指针交替移动。这三道题每道都能在 15 分钟内写完连续刷三天保证你的指针感有明显提升。等你回头看 143 题会发现它不再是一道“吓人”的难题而是三个你已经掌握的模板文件的组合写起来行云流水。我个人在实际刷题中最受益的一个习惯是每次做完一道组合题就在笔记里写一句话总结“这道题是由哪些基础题拼起来的”。积累一段时间后再回看你会发现自己面对新题时的拆解速度变快了不是因为你见过所有题而是因为你见过的“零件”足够多。143 题就是这样一个标准的“零件箱”题目吃透它对你后续刷很多链表题的帮助远超它本身的分值。
