LeetCode 补充题 1. 排序奇升偶降链表
目录
题目描述
题意分析
输入不是一条普通乱序链表，题目给了一个很强的前提：从表头开始按位置编号，奇数位上的节点从前往后是升序，偶数位上的节点从前往后是降序，两组数据交错穿插在同一条链上。要求返回一条把全部节点整体按升序排好的链表。
这个前提就是最大的约束信号。它意味着数据其实已经是「有序的」，只是被拆成两串并且其中一串方向相反——所以不该把它当成一道普通排序题从零开始排，而应该想办法把这两串已有的顺序利用起来。另一处信号是「排序链表」而非「排序数组」：返回值是链表，节点应当被重新串联而不是重建，答案里也不允许出现新的节点值副本。
边界要提前想清楚。链表为空或只有一个节点时原样返回。只有两个节点时，偶数位那串只有一个元素，反转后仍是它自己，逻辑照常成立。节点总数为奇数时，奇数位那串比偶数位那串多一个，两串长度不等是常态，收尾必须能处理其中一串先走完的情况。此外，两串之间的值可能相等，为保持稳定性以及避免遗漏，比较时要用「小于等于」而不是「小于」。
解法：拆分奇偶链表后反转合并
核心思路
问题关键：原链表不是完全无序，而是两条链交错：奇数位置已经升序，偶数位置已经降序。若把节点值复制到数组后排序，会浪费这一结构，并产生 $O(n\log n)$ 时间和 $O(n)$ 空间。
为什么选拆分、反转、归并：先按位置拆出奇数链和偶数链；反转降序的偶数链，使两条链都升序；最后复用合并有序链表的双指针方法。三段都只改指针，各做一趟即可。
不变量：拆分时，
odd、even分别是两条已拆链的尾节点，链内相对顺序不变；反转时，pre始终是已反转部分的头；归并时，dummy.next到tail始终是已经确定的升序前缀。正确性：拆分后两条链分别保留原奇数位升序和偶数位降序；反转只改变偶数链方向，因此得到两条升序链。归并每次选择两个链头中较小者，它不大于两条链中所有未处理节点，所以追加后升序前缀仍成立。所有节点最终恰好被接入一次，结果既完整又有序。
解题步骤
- 空链或单节点直接返回；否则保存偶数链头
evenHead = head.next。- 用
odd、even交替改写next，拆出两条链。循环结束后执行odd.next = null，彻底断开奇数链尾部。- 原地反转
evenHead，将偶数位降序链变成升序链。- 用哑结点和双指针合并两条升序链；一条耗尽后，直接接上另一条剩余部分。
- 口述样例：
1→8→3→6→5→4拆成1→3→5与8→6→4；后者反转为4→6→8；归并得到1→3→4→5→6→8。
代码实现
class Solution {
public ListNode sortOddEvenList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = null;
// 偶数位置原本降序，反转后变为升序。
ListNode sortedEven = reverse(evenHead);
return merge(head, sortedEven);
}
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 ListNode merge(ListNode first, ListNode second) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (first != null && second != null) {
if (first.val <= second.val) {
tail.next = first;
first = first.next;
} else {
tail.next = second;
second = second.next;
}
tail = tail.next;
}
if (first != null) {
tail.next = first;
} else {
tail.next = second;
}
return dummy.next;
}
}
func sortOddEvenList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
odd := head
even := head.Next
evenHead := even
for even != nil && even.Next != nil {
odd.Next = even.Next
odd = odd.Next
even.Next = odd.Next
even = even.Next
}
odd.Next = nil
// 反转偶数位置链表后，与奇数链表做有序合并。
sortedEven := reverseList(evenHead)
return mergeLists(head, sortedEven)
}
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 mergeLists(first *ListNode, second *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for first != nil && second != nil {
if first.Val <= second.Val {
tail.Next = first
first = first.Next
} else {
tail.Next = second
second = second.Next
}
tail = tail.Next
}
if first != nil {
tail.Next = first
} else {
tail.Next = second
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$。拆分、反转和归并各自至多线性遍历节点。
- 空间复杂度：$O(1)$。只使用固定数量的指针，所有节点都原地重连。
关键点总结
- 利用“奇升偶降”比通用排序更重要，三步模板是：拆分、反转、归并。
- 题目说的是位置奇偶，不是节点值奇偶。
- 拆链后必须显式断尾；需要后续复用的链头要提前保存。
- 归并用哑结点消除新头分支，比较用
<=可让相等值稳定地取自第一条链。
易错点总结
- 忘记断开奇数链尾部：两条链会共享节点，反转或归并后可能形成环。
- 未保存
evenHead：拆分游标会移动到链尾，之后无法从头反转完整偶数链。- 循环条件缺少
even.next != null：偶数链走到尾部时会通过空指针访问下一节点。- 省略反转直接归并：
1→8→3→6→5→4会得到带降序尾巴的错误结果。- 按节点值奇偶拆分：题目约束的是位置，节点值本身与分组无关。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 21. 合并两个有序链表 | 简单 | 本题第三段的原型，哑结点加双指针归并 |
| 206. 反转链表 | 简单 | 本题第二段的原型，三指针原地反转 |
| 328. 奇偶链表 | 中等 | 本题第一段的原型，拆完后是首尾相接而非归并 |
| 143. 重排链表 | 中等 | 同为拆分加反转，但收尾是交叉穿插而不是比较 |
| 234. 回文链表 | 简单 | 拆半加反转后逐位比对，只读不重连 |
| 148. 排序链表 | 中等 | 不给任何有序前提，需要自底向上的归并排序 |
| 23. 合并 K 个升序链表 | 困难 | 归并从两路扩展到多路，靠堆或分治降低比较次数 |
| 147. 对链表进行插入排序 | 中等 | 每个节点都要回到已排好的前缀里找插入位置 |