LeetCode 补充题 1. 排序奇升偶降链表
题目描述
给定单链表的头节点
head。从第1个节点开始计数，奇数位置上的节点值按升序排列，偶数位置上的节点值按降序排列。请重新连接这些节点，使整条链表按节点值升序排列，并返回排序后的头节点。
示例 1：
输入：head = [1,8,3,6,5,4,7,2]
输出：[1,2,3,4,5,6,7,8]
提示：
- 奇数位置和偶数位置指的是节点的位置，不是节点值的奇偶性。
- 排序后保留所有原节点，不遗漏或重复节点。
- 尝试在 O(n) 时间和 O(1) 额外空间内完成。
题意分析
链表从第
1个节点开始计数，奇数位置上的节点按升序排列，偶数位置上的节点按降序排列。要求调整节点连接，让整条链表按升序排列，并保留全部节点。“奇偶”描述的是位置，不是节点值的奇偶。输入并非完全无序，而是两条方向相反的有序序列交错在一起，应利用这条限制来完成排序。
解法：拆分奇偶链表后反转合并
核心思路
[!blue]
先按位置把链表拆成奇数链和偶数链，并保持每一组内部的原始顺序。这样奇数链天然升序，偶数链天然降序，不需要重新比较组内所有节点。
将偶数链原地反转后，它也变成升序链。问题便转化为合并两条有序链表：每次比较两个链头，把较小的节点接到结果末尾。因为每条链头都是本链剩余节点中的最小值，所以两者中较小者也就是全部未处理节点中的最小值，逐次接入就能保持结果有序。
拆分时，
odd和even分别维护两条链的尾节点，通过跳过另一组节点来延长本组连接。提前保存evenHead，避免游标走到尾部后丢失偶数链入口；拆分结束还要令odd.next = null，清除偶数长度时奇数链尾部可能保留的跨组连接。两条链完全分开后再反转、归并，才能保证每个原节点只属于一个输入，既不会丢节点，也不会在重复接入同一节点时成环。归并到一条链耗尽，另一条链剩余部分已经有序，直接整体接上即可。
解题步骤
- 空链表或只有一个节点时，直接返回原头节点。
- 令
odd指向头节点，even指向第二个节点，并保存evenHead。- 交替跳过偶数、奇数位置节点，分别延长两条链；循环结束后断开奇数链尾部的旧连接。
- 从
evenHead开始反转偶数链，得到第二条升序链。- 使用哑节点和结果尾指针，逐次接入两条链中较小的头节点；一条链耗尽后接入另一条剩余部分，返回哑节点的后继。
代码实现
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)$。只使用固定数量的指针，所有节点都原地重连。
关键点总结
[!green]
- 拆分保留组内顺序，反转统一排序方向，归并得到整体升序。
- 先保存入口、再移动游标，拆完显式断尾，保证后续处理的两条链互不共享节点。
- 相等时先接哪一条链都满足升序；但反转偶数链可能改变相等节点的原始相对顺序，整个算法不保证稳定性。
易错点总结
[!yellow]
- 按节点值奇偶分组，无法利用题目给定的位置顺序，拆出的链不一定有序。
- 未保存偶数链头，拆分指针移到末尾后就无法重新找到反转起点。
- 忘记断开奇数链尾部，两条待合并链可能仍共享最后的偶数节点，后续重连可能成环。
- 反转时没有先保存原后继，就会丢失尚未处理的节点。
- 偶数链仍是降序时就直接归并，链头不再代表剩余最小值，合并有序性不成立。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 328. 奇偶链表 | 中等 | 按位置奇偶拆成两条链是基础，本题还利用两条链原有的相反单调方向。 |
| 21. 合并两个有序链表 | 简单 | 偶数位置链反转成升序后，复用两条有序链表归并；不必对全链做通用排序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！