#143 / LCR 026. 重排链表

• LeetCode：143. 重排链表 · LCR 026. 重排链表
• 难度：中等
• 归类：链表、快慢指针、反转链表
• 主解法：寻找中点 + 反转后半部分 + 交替合并

#先给结论

单链表不能从尾部向前遍历，而目标顺序要求依次取出“头、尾、次头、次尾”。解决办法是：

1. 用快慢指针找到前半部分的末尾并断开链表。
2. 反转后半部分，使原链表的尾节点可以从前往后访问。
3. 将前半部分和反转后的后半部分交替合并。

整个过程只修改节点的 next 指针，不修改节点值，时间复杂度为 O(n)，额外空间复杂度为 O(1)。

#题目描述

给定单链表：

L0 → L1 → … → Ln-1 → Ln

将它重新排列为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只交换节点中的值，必须实际调整节点之间的连接关系。函数没有返回值，需要原地修改以 head 开始的链表。

示例 1：

输入：1 → 2 → 3 → 4
输出：1 → 4 → 2 → 3

示例 2：

输入：1 → 2 → 3 → 4 → 5
输出：1 → 5 → 2 → 4 → 3

题目约束：

• 链表长度在 [1, 5 × 10^4] 范围内。
• 1 <= node.val <= 1000。

#问题本质

如果把所有节点存入数组，就能用首尾下标交替取节点，但需要 O(n) 额外空间。

要把空间降到 O(1)，关键是把链表后半部分反转。假设原链表被拆成：

前半部分：L0 → L1 → L2
后半部分：L3 → L4 → L5

反转后半部分后得到：

L5 → L4 → L3

此时两个链表都只需向前遍历，交替取节点就能得到：

L0 → L5 → L1 → L4 → L2 → L3

因此，本题不是在两个候选之间进行比较，而是通过改变后半部分的遍历方向，将问题转化为两个链表的交替合并。

#算法步骤

#第一步：找到前半部分的末尾

让 slow 每次走一步，fast 每次走两步：

while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
}

循环结束时，slow 位于前半部分的最后一个节点：

• 节点数为偶数时，两部分长度相等。
• 节点数为奇数时，前半部分比后半部分多一个节点。

所以后半部分的节点数始终不会超过前半部分，交替合并时 first 不会提前变成 null。

#第二步：断开并反转后半部分

先保存后半部分的头节点，再将 slow.next 设为 null：

let second = slow.next;
slow.next = null;

断开非常重要。如果不断开，合并过程中旧连接仍然存在，容易形成环。

随后使用反转链表的标准写法，将 second 指向的链表反转。

#第三步：交替合并

每轮分别从两个链表中取出一个节点：

first → second → firstNext

修改指针前必须先保存 firstNext 和 secondNext，否则后续尚未处理的链表会丢失。

#示例推演

以 1 → 2 → 3 → 4 → 5 为例：

最终结果：

1 → 5 → 2 → 4 → 3

对于偶数长度 1 → 2 → 3 → 4：

拆分：1 → 2    3 → 4
反转：1 → 2    4 → 3
合并：1 → 4 → 2 → 3

#代码实现

参考实现来源：doocs/leetcode，按本文结构重新整理；原项目采用 CC BY-SA 4.0。

#JavaScript 实现

/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
    if (!head || !head.next) {
        return;
    }

    // 1. 找到前半部分的最后一个节点
    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. 断开链表并反转后半部分
    let second = slow.next;
    slow.next = null;

    let prev = null;
    while (second) {
        const next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }

    // 3. 交替合并两个链表
    let first = head;
    second = prev;
    while (second) {
        const firstNext = first.next;
        const secondNext = second.next;

        first.next = second;
        second.next = firstNext;

        first = firstNext;
        second = secondNext;
    }
};

#代码与思路对照

#正确性说明

可以分三步说明：

1. 拆分正确。 快指针每次走两步，慢指针每次走一步。循环结束时，slow 停在前半部分末尾；断开后，前半部分长度等于后半部分，或比后半部分多一。
2. 反转正确。 反转完成后，第二条链表依次为 Ln、Ln-1、Ln-2、…，正好是目标顺序中需要穿插的节点顺序。
3. 合并正确。 每轮先连接一个前半部分节点，再连接一个反转后的后半部分节点，因此已合并前缀始终满足 L0 → Ln → L1 → Ln-1 → …。后半部分耗尽时，所有需要穿插的节点都已处理；如果总节点数为奇数，前半部分剩余的最后一个节点自然位于链表末尾。

所以算法最终得到题目要求的重排链表。

#边界与陷阱

• 空链表和单节点： 官方约束保证链表非空，但提前返回可以让实现更加健壮。
• 两个节点： 后半部分只有一个节点，合并后链表顺序不变。
• 奇数长度： 前半部分会多一个节点，最后的中间节点无需额外处理。
• 必须先断链： 忘记执行 slow.next = null 可能保留旧连接并形成环。
• 先保存后继节点： 合并时必须先保存两边的 next，再修改连接。
• 不能只交换值： 题目要求重连节点，节点值即使重复也不影响算法。

#复杂度分析

• 时间复杂度：O(n)。寻找中点、反转和合并都只会线性遍历链表。
• 额外空间复杂度：O(1)。只使用有限个指针变量。

#面试官递进追问

#1. 为什么要反转后半部分？

单链表只能向后遍历。反转以后，原来的尾节点会变成第二条链表的头节点，从而能按照 Ln、Ln-1、… 的顺序在线性时间内访问。

#2. 为什么快慢指针的条件是 fast.next && fast.next.next？

这个条件让 slow 停在前半部分的最后一个节点。对于奇数长度，前半部分多一个节点；对于偶数长度，两部分等长，因此合并时后半部分不会比前半部分更长。

#3. 为什么必须执行 slow.next = null？

它将两部分彻底分开。若保留原来的连接，反转和交替合并时可能让某个节点同时指向已处理部分和未处理部分，最终形成环。

#4. 合并阶段维护什么不变量？

每轮开始前，已经合并的前缀符合 L0 → Ln → L1 → Ln-1 → …；first 和 second 分别指向两部分中下一个尚未合并的节点。

#5. 为什么合并循环只判断 second？

拆分后，后半部分的长度不会超过前半部分。只要后半部分还有节点，前半部分就一定有可与之配对的节点；后半部分耗尽时重排已经完成。

#6. 能否使用额外空间简化实现？

可以把所有节点放进数组，再用左右下标交替重连。时间复杂度仍为 O(n)，但额外空间复杂度变为 O(n)，优点是实现更直观。

#7. 能否把寻找中点的条件改成 fast && fast.next？

不能只替换循环条件而保持其他代码不变。对于偶数长度链表，新条件会让 slow 停在后半部分的第一个节点，而当前代码需要它停在前半部分的最后一个节点。如果采用新条件，还需要用额外指针记录 slow 的前驱，并从前驱位置断开链表。

#8. 时间复杂度还能低于 O(n) 吗？

不能。单链表没有尾指针和反向指针，要找到尾部节点至少需要从头遍历一次，因此最坏情况下存在 Ω(n) 的时间下界。当前实现已经达到渐进最优。

#常见错误

• 把 slow 停在错误位置，导致后半部分比前半部分长。
• 反转前没有断开链表，最终产生环。
• 修改 next 之前没有保存后继节点，导致剩余链表丢失。
• 合并时连续修改多个指针却没有区分两边的下一节点。
• 只交换节点值，没有实际调整节点连接关系。
• 忘记函数返回 void，错误地依赖返回值获取结果。

#可迁移总结

• 找中点： 快慢指针可以在线性时间内把链表分成长度接近的两部分。
• 改变访问方向： 单链表无法从尾部向前访问时，可以考虑反转链表。
• 原地合并： 修改指针前先保存后继节点，避免丢失未处理部分。
• 一句话记忆： 找中点并断链，反转右半边，再交替合并。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么反转后半部分后，就可以只向前遍历完成重排？