如何重排链表为 L0→Ln→L1→Ln-1 的形式？

简化版

重排链表常用三步：快慢指针找到中点，把后半段反转，再把前半段和反转后的后半段交替合并。整个过程时间 O(n)，额外空间 O(1)。

详细版

例如：

1 -> 2 -> 3 -> 4 -> 5
重排后:
1 -> 5 -> 2 -> 4 -> 3

做法是先找到中点 3，把后半段 4 -> 5 反转成 5 -> 4，再和前半段 1 -> 2 -> 3 交替连接。面试要强调：不是交换节点值，而是调整节点指针；合并前要断开前后两段，避免形成环。

完整版教学

一、重排链表本质是首尾交替

题目要求把链表：

L0 -> L1 -> L2 -> ... -> Ln

变成：

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ...

链表不能像数组那样 O(1) 访问尾部，所以不能每次从尾巴取节点。更好的办法是把后半段整体反转，让尾部节点变成容易顺序访问的链表。

记忆钩子：先找中点，再反后半，最后拉拉链。

二、第一步用快慢指针找中点

快指针一次走两步，慢指针一次走一步。快指针到尾部时，慢指针在中间。

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
  slow = slow.next;
  fast = fast.next.next;
}

对于 1->2->3->4->5，slow 最后在 3。对于 1->2->3->4，slow 最后在 2。

这能保证前半段长度大于或等于后半段，交替合并时更方便。

三、第二步反转后半段

找到中点后，把后半段切下来：

ListNode second = slow.next;
slow.next = null;

然后反转 second：

before:
1 -> 2 -> 3    4 -> 5

after reverse:
1 -> 2 -> 3    5 -> 4

断开 slow.next 很重要。如果不断开，后面交替合并时可能形成环或保留旧连接。

四、第三步交替合并两段链表

现在有两条链表：

first:  1 -> 2 -> 3
second: 5 -> 4

合并时每次从 second 取一个插到 first 后面：

while (second != null) {
  ListNode next1 = first.next;
  ListNode next2 = second.next;

  first.next = second;
  second.next = next1;

  first = next1;
  second = next2;
}

过程：

1 -> 5 -> 2 -> 4 -> 3

因为前半段长度不小于后半段，循环条件用 second != null 就够了。

五、为什么不能简单交换值

有些题目允许改节点值，但链表题通常希望你调整指针。交换值会有几个问题：

问题	说明
节点可能存复杂对象	复制成本高或语义不对
外部可能引用节点	节点身份不应被值替换
题目明确要求重排节点	交换值不符合要求

面试里优先按“改指针”回答，除非题目明确允许交换值。

六、复杂度和边界

找中点 O(n)，反转后半段 O(n)，合并 O(n)，总时间仍是 O(n)。只用常数个指针，额外空间 O(1)。

边界：

空链表 -> 不处理
1 个节点 -> 不处理
2 个节点 -> 不处理或自然保持
奇数长度 -> 中点留在最后
偶数长度 -> 两段一样长

代码开始可以写：

if (head == null || head.next == null) return;

七、常见误区与追问

误区：重排链表就是交换节点值。 高频面试语义通常是调整节点指针，不改值。
误区：找中点后不用断开。 不断开前后段，交替合并可能形成环。
误区：后半段不反转也能顺序取尾节点。 单链表从尾部取节点不方便，会导致 O(n²)。
追问：为什么用快慢指针？ 单次遍历找到中点，避免先统计长度再走一遍。
追问：为什么合并循环看 second？ 前半段长度不小于后半段，second 用完就完成重排。
追问：复杂度是多少？ 时间 O(n)，额外空间 O(1)。

八、加强记忆

重排链表记成“三段式操作”：快慢指针找中点，切开并反转后半段，最后像拉链一样交替合并。关键边界是要断开中点后的旧连接，合并时保存 next1 和 next2，避免丢链。它考的是链表指针组织能力，不是数组式首尾随机访问。

简化版

详细版