重排链表
Reorder List
本机进度仅保存在当前浏览器
题目描述
给定单链表 L：L0 -> L1 -> ... -> Ln-1 -> Ln，重排为 L0 -> Ln -> L1 -> Ln-1 -> ...。不能只改节点值，必须实际交换节点，要求原地完成。
示例：1 -> 2 -> 3 -> 4 -> 5 重排为 1 -> 5 -> 2 -> 4 -> 3。
解题思路
- 目标序列是"前半段正序 + 后半段逆序"交错，因此拆成三步经典操作的组合。
- 第一步快慢指针找中点，把链表一分为二；第二步反转后半段；第三步把两段按"前一个 + 后一个"交错合并。
- 三个子操作都是链表基本功（206 反转、876 中点、21 合并），组合即解，注意断开中点前先断链防环。
参考实现
查看参考实现Python · 建议先自行作答
def reorderList(head):
# 1. 快慢指针找中点
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = None
# 2. 反转后半段
prev = None
while second:
nxt = second.next
second.next = prev
prev = second
second = nxt
# 3. 交错合并两段
p, q = head, prev
while q:
nxt = q.next
q.next = p.next
p.next = q
p = q.next
q = nxt