LeetCode LCR 026. 重排链表
目录
题目描述
题意分析
给定链表
L0 → L1 → ... → Ln-1 → Ln，把它就地重排成L0 → Ln → L1 → Ln-1 → L2 → ...，即首尾交替取节点，直到全部用完。题目明确要求不能只改节点的值，必须实际改变节点之间的连接。这条约束否掉了「把值倒进数组再按新顺序写回值」的偷懒解法，逼你真正操作指针。
观察目标形态可以发现一个结构性事实：新链表是把原链表从中间劈成两半，后半段倒过来，再与前半段一交一叉地缝合。前半段保持原序，后半段完全逆序，交替时永远是前半段先出。
长度奇偶要分清。长度为偶数时两半等长；长度为奇数时中间那个节点应当留在前半段（它是最后一个被输出的），否则拼接时会多出一个节点无处安放。这决定了「中点」要往哪一侧取。
边界：空链表和单节点链表本身就是答案；两个节点时结果与输入相同。这些都应该被主逻辑自然覆盖。
解法：双指针收缩边界
核心思路
暴力做法是把所有节点指针存进数组，然后用左右两个下标交替取节点重新串起来，$O(n)$ 时间但需要 $O(n)$ 额外空间。它虽然直白，却暴露了真正的瓶颈：我们之所以需要数组，是因为单链表无法从尾部往前取节点。
把需求拆开看，「交替取首尾」等价于三个独立的、都能就地完成的动作：把链表劈成前后两段、把后半段反转、把两段交替合并。反转之后，「从尾往前取」就变成了「从新的头往后取」，方向冲突彻底消失，数组也就不需要了。
三步各自的不变量如下。
第一步找中点：
slow每次走一步、fast每次走两步，两者从同一个头出发，不变量是「fast走过的步数恒为slow的两倍」。循环在fast或fast.next为空时结束，此时slow停在前半段的最后一个节点上。长度为奇数时它就是正中间那个，长度为偶数时它是靠左的那个——两种情况都保证了前半段长度不小于后半段，这正是交替合并所需要的。第二步反转后半段：把
slow.next之后的部分整体反转，同时执行slow.next = null断开两段。断开这一步不能省——不断开的话，反转后前半段的尾部仍指向后半段的旧尾，合并时会绕成环。第三步交替合并：维护
cur作为结果链表的尾部，每轮先接一个前半段节点、再接一个后半段节点。因为前半段长度不小于后半段，循环以「后半段耗尽」告终，最后把前半段可能剩下的一个节点接到尾部即可收尾。
解题步骤
- 找中点：
slow与fast同起于head，循环条件fast != null && fast.next != null。两个判空缺一不可，因为fast一次跳两格，两个位置都可能踩空。循环结束时slow是前半段的末节点。- 暂存并断开：先
tmp = mid.next拿到后半段入口，再mid.next = null。顺序不能反，先断开就再也找不到后半段了。- 反转后半段：用
pre、cur、tmp三指针原地反转，每轮先暂存后继再改next。反转后pre是后半段的新头，即原链表的尾节点。- 交替合并：
dummy作锚点，cur作尾巴。每轮固定「接l1一个、再接l2一个」，且每接一次都要把对应的指针往后挪并更新cur。这个顺序对应题目要求的L0 → Ln → L1 → ...，先接后半段就会得到反过来的排列。- 收尾：循环因
l2耗尽而退出时，l1可能还剩一个节点（原链表长度为奇数或偶数时的尾巴），用cur.next = l1 != null ? l1 : l2一句挂上。这一步同时把结果链表的末端封死，避免残留旧指针形成环。- 函数无返回值：重排是就地完成的，
head始终是结果的头节点，所以合并函数的返回值可以不接。以
1 → 2 → 3 → 4 → 5走一遍。找中点：slow = 1, fast = 1→slow = 2, fast = 3→slow = 3, fast = 5；此时fast.next为空，退出，mid = 3。暂存tmp = 4，断开得到前半段1 → 2 → 3与后半段4 → 5。反转后半段得到5 → 4。合并：
l1 = 1 → 2 → 3，l2 = 5 → 4。第一轮接1，再接5，结果为1 → 5，l1 = 2、l2 = 4。第二轮接2，再接4，结果为1 → 5 → 2 → 4，l1 = 3、l2 = null。循环退出，l1还剩节点3，挂到尾部得1 → 5 → 2 → 4 → 3，与题目要求一致。再看偶数长度
1 → 2 → 3 → 4：找中点得slow = 3，前半段1 → 2 → 3、后半段4，反转后仍是4。合并第一轮接1再接4，l1 = 2 → 3、l2 = null，退出后把2 → 3整体挂上，得1 → 4 → 2 → 3，正确。最小用例
1：找中点得slow = 1，tmp = null，断开后前半段仍是1、后半段为空，反转空链得空，合并循环一次不进，直接把l1挂到dummy后，结果仍是1，无需特判。
代码实现
class Solution {
public void reorderList(ListNode head) {
ListNode mid = middleNode(head);
// 先存后继再断开，否则后半段丢失。
ListNode tmp = mid.next;
mid.next = null;
tmp = reverseList(tmp);
head = mergeTwoLists(head, tmp);
}
private ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
// 结束时 slow 停在前半段末尾，保证前半段不短于后半段。
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode cur = dummy;
// 固定「先接前半段、再接后半段」，对应 L0 → Ln → L1 → ...
while (l1 != null && l2 != null) {
cur.next = l1;
l1 = l1.next;
cur = cur.next;
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dummy.next;
}
}
func reorderList(head *ListNode) {
mid := middleNode(head)
// 先存后继再断开，否则后半段丢失。
tmp := mid.Next
mid.Next = nil
tmp = reverseList(tmp)
head = mergeTwoLists(head, tmp)
}
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
// 结束时 slow 停在前半段末尾，保证前半段不短于后半段。
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := new(ListNode)
cur := dummy
// 固定「先接前半段、再接后半段」，对应 L0 → Ln → L1 → ...
for l1 != nil && l2 != nil {
cur.Next = l1
l1 = l1.Next
cur = cur.Next
cur.Next = l2
l2 = l2.Next
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
}
if l2 != nil {
cur.Next = l2
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$。找中点扫半条链，反转扫后半条，合并扫全部节点各一次，三段都是线性且互不嵌套，循环体内全是常数次指针赋值。
- 空间复杂度：$O(1)$。三个子过程各自只用了固定几个指针变量，没有数组也没有递归栈；这正是它相对「节点指针存数组」解法的价值所在。
关键点总结
- 复杂的重排需求先拆成若干个已知的原子操作，「找中点 + 反转 + 合并」这套组合是链表题里复用率最高的三件套。
- 反转的真正作用是把「从尾往前取」转成「从头往后取」，凡是遇到链表需要逆向访问又不许开额外空间，就往这个方向想。
- 中点要取在偏左的位置，让前半段不短于后半段，合并循环才能以「后半段先耗尽」这一种方式结束，收尾只需一句。
- 断开两段是必须的独立步骤，不是可选的收尾；不断开会在合并时形成环，遍历结果时死循环。
- 每一个子过程都保持「先暂存后继、再改
next」的铁律，链表题的绝大多数崩溃都来自违反这一条。- 面试视角：可以先说数组解法证明思路可行，再指出题目要求就地改指针、且额外空间应为 $O(1)$，然后拆成三步逐个写。三个子函数分开写比塞进一个函数更容易讲清楚，也更容易在白板上定位问题。
易错点总结
- 先执行
mid.next = null再取tmp：1 → 2 → 3 → 4 → 5会拿到空的后半段，结果原样输出1 → 2 → 3，尾部两个节点丢失。- 完全不断开两段：合并时前半段末节点仍指向后半段旧尾，
1 → 2 → 3 → 4会拼出带环的链表，判题遍历时死循环。- 中点取在偏右位置（
fast从head.next起步并按此切分）：后半段比前半段长，合并循环退出时剩下的是l2，若收尾只写cur.next = l1就会丢节点。- 合并时先接后半段再接前半段：
1 → 2 → 3 → 4 → 5会得到5 → 1 → 4 → 2 → 3，首节点就错了。- 合并循环里忘记更新
cur：每轮都在同一个位置改next，1 → 2 → 3 → 4只会保留最后接上的两个节点。- 收尾漏掉
cur.next = l1：1 → 2 → 3 → 4 → 5会输出1 → 5 → 2 → 4，最后的节点3被丢弃。- 找中点时循环条件只写
fast.next != null：偶数长度链表如1 → 2上fast先变成空，再取fast.next直接空指针异常。- 只交换节点的值而不改指针：题目明令禁止，且节点若带有其他字段方案根本不成立。
- 反转子过程里忘记暂存
cur.next：后半段4 → 5在第一轮就断成孤立的4，合并结果丢失节点5。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 143. 重排链表 | 中等 | 与本题同题，可直接套用三步拆解 |
| 206. 反转链表 | 简单 | 只做本题的第二步，是三件套里最基础的一件 |
| 234. 回文链表 | 简单 | 同样是「找中点 + 反转后半段」，但第三步换成逐位比对而非交替缝合 |
| 2130. 链表最大孪生和 | 中等 | 同样的前两步，第三步改成对应位置求和取最大值 |
| 21. 合并两个有序链表 | 简单 | 只做本题的第三步，但推进依据是值的大小而非严格交替 |
| 328. 奇偶链表 | 中等 | 反过来做：把一条链按位置拆成两条再首尾相接，是本题合并动作的逆操作 |
| 86. 分隔链表 | 中等 | 同样先拆两条链再拼接，但拆分依据是节点值与阈值的比较 |