LeetCode 328. 奇偶链表
目录
题目描述
题意分析
给定一条单链表，把处于奇数序号（第 1、3、5……个）的节点集中到前面，处于偶数序号的节点接在后面，返回重排后的头节点。
这里的「奇偶」指的是节点在链表中的位置序号，与节点保存的值没有任何关系；两组节点各自内部的相对先后顺序必须保持不变，不能打乱。
题目额外要求 $O(1)$ 的空间与 $O(n)$ 的时间。这个约束很关键：它排除了「先把节点值抄进数组、重排后再写回」的做法，也排除了任何需要新建节点的方案，只能靠改写已有节点的
next指针完成。需要留意的边界情形：空链表；只有一个节点；恰好两个节点（重排后与原链表相同）；长度为奇数与为偶数时，遍历的收尾位置不一样。
解法：原地拆分奇偶位置链表
核心思路
问题关键： 题目按节点的位置奇偶分组，并要求两组内部的相对顺序不变，还要使用 $O(1)$ 额外空间。因此不能复制节点或按值排序，只能原地改
next。为什么选择双链拆分： 遍历时节点本就按奇、偶位置交替出现。用
odd、even分别指向两条子链的尾节点，每轮各接入一个节点，最后把奇数链尾接到偶数链头即可。不变量： 每轮开始时，
odd是已整理奇数位置节点的尾部，even是已整理偶数位置节点的尾部；两条子链都保持原相对顺序，evenHead始终指向偶数链头。正确性：
even.next是下一个奇数位置节点，把它接到odd后不会改变奇数节点的先后顺序；新的odd.next是下一个偶数位置节点，同理接到even后保持偶数节点顺序。每轮处理一对节点且不遗漏。循环结束时所有节点已分别进入两条链，执行odd.next = evenHead后，结果正是“全部奇数位置节点 + 全部偶数位置节点”。
解题步骤
- 空链表直接返回；否则令
odd = head、even = head.next，并用evenHead保存偶数链入口。- 当
even != null && even.next != null时，先令odd.next = even.next并推进odd。- 再令
even.next = odd.next并推进even。两步顺序不能交换，因为第二步依赖推进后的odd.next。- 循环结束后，把
odd.next指向evenHead，返回原头节点。口述示例：
1 → 2 → 3 → 4 → 5被逐步拆成奇数链1 → 3 → 5和偶数链2 → 4，最后连接为1 → 3 → 5 → 2 → 4。边界与反例： 长度为 1 或 2 时循环不会执行，最后拼接仍正确。不要把“奇偶”理解成节点值：
2 → 1 → 4 → 3的正确结果按位置应是2 → 4 → 1 → 3。
代码实现
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
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 = evenHead;
return head;
}
}
func oddEvenList(head *ListNode) *ListNode {
if head == nil {
return nil
}
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 = evenHead
return head
}
复杂度分析
- 时间复杂度为 $O(n)$：每个节点只被访问和连接常数次。
- 额外空间复杂度为 $O(1)$：只维护三个指针，不创建新节点。
关键点总结
- 分组重排链表时，“拆成稳定子链再拼接”通常比逐节点交换更直接。
evenHead必须在改链前保存，否则循环后找不到偶数链入口。- 循环条件由循环体要访问的最远指针
even.next决定。- 多个指针连续赋值时，要按依赖顺序更新；本题必须先推进
odd，再改even.next。
易错点总结
- 未判空就读取
head.next：空链表会直接报错。- 只判断
even != null：长度为 2 时会把odd推进到空节点，再继续解引用。- 不保存
evenHead：head.next会在循环中被改写，最后可能丢链或成环。- 漏掉最后的
odd.next = evenHead：结果只剩奇数位置子链，偶数节点无法到达。- 交换四条赋值语句的顺序：会读取已被覆盖的后继，造成节点丢失或链表成环。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 24. 两两交换链表中的节点 | 中等 | 同样只动指针，但要相邻两节点互换而非分成两条链，通常需要哑节点承接新头 |
| 61. 旋转链表 | 中等 | 先首尾成环再按长度取模断开，重点是定位断点而不是按规则分组 |
| 86. 分隔链表 | 中等 | 同样是拆两条链再拼接，但分组依据是节点值与 x 的大小关系，而非位置 |
| 143. 重排链表 | 中等 | 需要找中点、反转后半段、再交替归并，是三个链表基本操作的组合 |
| 725. 分隔链表 | 中等 | 按总长度均分成 $k$ 段并返回头节点数组，难点在每段长度的计算与逐段断尾 |
| 2130. 链表最大孪生和 | 中等 | 同样要处理链表的前后两半，但目标是求最大配对和，不改变链表结构 |
| 面试题 02.04. 分割链表 | 中等 | 与 86 题同源但不要求保持相对顺序，可用头插法进一步简化 |