LeetCode 143. 重排链表
题目描述
题意分析
将链表按原来的第一个、最后一个、第二个、倒数第二个的顺序交替连接，直到所有节点都被使用。必须原地调整节点的
next，不能只交换节点值；函数不返回新链表，因为重排后的第一个节点仍是原头节点。需要的节点来自两端：前半部分按原顺序读取，后半部分按反向顺序读取。单链表只能向后走，如果每次重新寻找尾节点会反复遍历，因此先把链表拆成两段，再反转后半段，就能把两端交替取节点转成两个指针向前移动。
解法：找中点 + 反转后半段 + 交替合并
核心思路
[!blue]
先将链表拆成前后两段，让前半段长度不少于后半段。使用从头出发的快慢指针，
slow每次走一步，fast每次走两步；只有fast后面还存在两个节点时才继续。长度为偶数时，slow停在左侧中点；长度为奇数时，停在唯一中点，中间节点归前半段。保存
second = slow.next后，将slow.next设为空，形成两条独立链表。必须先断开旧连接：接下来的反转和合并都把两段当作互不重叠的链表，若前半段仍能沿旧指针进入后半段，最后交叉连接时就可能重新接回已处理节点而形成环。接着反转后半段，使原尾节点成为这一段的新头。反转时，
pre指向已反转部分的头，cur指向下一个待处理节点；先保存原后继，再令cur.next = pre，最后推进两个指针。这样后半段就能按原链表从尾到中间的顺序依次读取。最后用
first、second分别指向两段当前尚未合并的节点，每轮把second插入first后面。先保存两边的后继firstNext、secondNext，再执行first.next = second、second.next = firstNext，随后分别沿保存的后继前进。保存后继的原因是两条当前连接都要改写，改写后再读取就不再是原来的剩余部分。每轮恰好取前半段一个节点和后半段一个节点，顺序正好对应从原链表两端向内交替。前半段至少一样长，因此只要
second非空，first就一定存在。后半段耗尽时，偶数长度的链表已经全部接好；奇数长度时，前半段只多出一个中间节点，它已经自然接在最后，且断链时已将其后继置空。
解题步骤
- 空链表或只有一个节点时直接结束。
- 快慢指针同时从头出发，用
fast.next和fast.next.next都非空作为继续条件，定位前半段尾节点slow。- 保存后半段头节点
second = slow.next，再断开slow.next。- 用迭代反转后半段，并让
second指向反转后的头节点。- 从原头节点和
second开始交替连接；每轮先保存两边后继，再修改连接，最后推进两个指针。- 后半段为空时结束，重排已经反映在原链表的节点连接中。
代码实现
class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = slow.next;
// 先断开两段的旧连接，后续交替合并才不会接回成环。
slow.next = null;
second = reverse(second);
merge(head, second);
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
// 反转前保存后继，避免丢失未处理部分。
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
private void merge(ListNode first, ListNode second) {
// 前半段长度不少于后半段，第二段耗尽就完成交替连接。
while (second != null) {
// 两段的后继都要先保存，再进行交叉连接。
ListNode firstNext = first.next;
ListNode secondNext = second.next;
first.next = second;
second.next = firstNext;
first = firstNext;
second = secondNext;
}
}
}
func reorderList(head *ListNode) {
if head == nil || head.Next == nil {
return
}
slow := head
fast := head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
second := slow.Next
// 先断开两段的旧连接，后续交替合并才不会接回成环。
slow.Next = nil
second = reverseList(second)
mergeList(head, second)
}
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
// 反转前保存后继，避免丢失未处理部分。
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
func mergeList(first *ListNode, second *ListNode) {
// 前半段长度不少于后半段，第二段耗尽就完成交替连接。
for second != nil {
// 两段的后继都要先保存，再进行交叉连接。
firstNext := first.Next
secondNext := second.Next
first.Next = second
second.Next = firstNext
first = firstNext
second = secondNext
}
}
复杂度分析
- 时间复杂度：$O(n)$，找中点、反转后半段和交替合并都只做线性次数的指针操作，几个阶段相加仍为线性时间。
- 空间复杂度：$O(1)$，只使用固定数量的指针，辅助函数均为迭代实现，没有递归栈。
关键点总结
[!green]
- 找中点后必须断链，否则合并时可能形成环。
- 修改
next前先保存后继，避免丢失剩余链表。- 合并循环以后半段是否为空为条件，可统一处理奇偶长度。
易错点总结
[!yellow]
- 忘记执行
slow.next = null，会保留旧连接并可能形成环。- 改指针前没有保存后继，会丢失尚未处理的节点。
- 快慢指针的循环边界写错，可能使后半段比前半段长。
- 空链表未提前返回会访问空指针；单节点用其余流程也能正确处理，入口提前返回只是省去无需进行的重排。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 876. 链表的中间结点 | 简单 | 快慢指针找中点是重排的第一步，之后才能拆成两半。 |
| 206. 反转链表 | 简单 | 反转后半段使尾部节点变得可顺序访问，再与前半段交替连接。 |
| 234. 回文链表 | 简单 | 拆分链表后反转并重新连接；本题从中点拆分并交替合并首尾，该题反转后半段后比较对称值。 |
| 92. 反转链表 II | 中等 | 拆分链表后反转并重新连接；本题从中点拆分并交替合并首尾，该题只反转指定区间。 |
| 25. K 个一组翻转链表 | 困难 | 拆分链表后反转并重新连接；本题从中点拆分并交替合并首尾，该题按固定长度分组反转。 |
| 补充题 108. 交替合并两个链表 | 简单 | 都交替接入两条链的节点；本题先找到中点并反转后半段，补充题直接给出两条链。 |