LeetCode 328中等链表
奇偶链表 图解题解
这道题到底在问什么
给定单链表头，把奇数位置节点全排到偶数位置节点前面，节点的相对先后保持原样。要求 O(1) 额外空间、O(n) 时间。
- 输入
- 1→2→…→9
- 输出
- 1→3→5→7→9→2→4→6→8
最优解：一步一步想明白
- 3核心就是「odd 接 odd、even 接 even」两条线交替往前缝，缝完把两条线拼起来。
- 4odd 指向奇链当前末尾（第 1 个节点，值 1），even 指向偶链当前末尾（第 2 个节点，值 2）。奇链先认下第 1 个（标绿）。oddHead 就是最终的新头。
- 5第 1 轮：odd 末尾是 1，even 末尾是 2。even 后面紧跟的是 3（它在奇位置）。要做 odd.next = even.next，把 3 接到奇链尾 1 后面。
- 6执行 odd.next = even.next：3 接到奇链尾后面（标绿入奇链），odd 前进到 3。现在奇链是 1→3。被抽走 3 后，原来 even 后面自然空出来，待会儿把它接到偶链。
- 7执行 even.next = odd.next：偶链尾 2 接上下一个偶位置节点 4，even 前进到 4。奇、偶两条线各往前缝了一格，进入下一轮。
- 8第 2 轮：odd 末尾是 3，even 末尾是 4。even 后面紧跟的是 5（它在奇位置）。要做 odd.next = even.next，把 5 接到奇链尾 3 后面。
- 9执行 odd.next = even.next：5 接到奇链尾后面（标绿入奇链），odd 前进到 5。现在奇链是 1→3→5。被抽走 5 后，原来 even 后面自然空出来，待会儿把它接到偶链。
- 10执行 even.next = odd.next：偶链尾 4 接上下一个偶位置节点 6，even 前进到 6。奇、偶两条线各往前缝了一格，进入下一轮。
- 11第 3 轮：odd 末尾是 5，even 末尾是 6。even 后面紧跟的是 7（它在奇位置）。要做 odd.next = even.next，把 7 接到奇链尾 5 后面。
- 12执行 odd.next = even.next：7 接到奇链尾后面（标绿入奇链），odd 前进到 7。现在奇链是 1→3→5→7。被抽走 7 后，原来 even 后面自然空出来，待会儿把它接到偶链。
- 13执行 even.next = odd.next：偶链尾 6 接上下一个偶位置节点 8，even 前进到 8。奇、偶两条线各往前缝了一格，进入下一轮。
- 14第 4 轮：odd 末尾是 7，even 末尾是 8。even 后面紧跟的是 9（它在奇位置）。要做 odd.next = even.next，把 9 接到奇链尾 7 后面。
- 15执行 odd.next = even.next：9 接到奇链尾后面（标绿入奇链），odd 前进到 9。现在奇链是 1→3→5→7→9。被抽走 9 后，原来 even 后面自然空出来，待会儿把它接到偶链。
- 16最后一步 odd.next = evenHead：把奇链尾 9 接到偶链头 2 上。奇链（1→3→5→7→9）在前、偶链（2→4→6→8）在后，正式拼成一条。
- 17重排完成：1→3→5→7→9→2→4→6→8。奇位置节点(1→3→5→7→9)全在前，偶位置(2→4→6→8)全在后，各自相对顺序不变。返回原头节点 1（它一直是奇链头）。
⚠️ 容易写错的地方
✗ 错：按节点的「值」奇偶分组
✓ 对：按节点的「位置」奇偶分组
题意是第几个节点，跟节点里存的数无关
✗ 错：忘了先存 evenHead
✓ 对：一开始就 even_head = even
循环里 even 会一直往后走，最后找不回偶链头，奇尾没法接
✗ 错：循环条件只写 while even
✓ 对：while even and even.next
even.next 为空时再取 even.next.next 会空指针；少了它最后一对会接错
完整代码（Python / C++ / Java）
Python
def oddEvenList(head):
if not head or not head.next:
return head
odd = head
even = head.next
even_head = even # 记住偶链头
while even and even.next:
odd.next = even.next # 奇链接下一个奇位置
odd = odd.next
even.next = odd.next # 偶链接下一个偶位置
even = even.next
odd.next = even_head # 奇尾接偶头
return headC++
ListNode* oddEvenList(ListNode* head){
if(!head || !head->next) return head;
ListNode *odd = head, *even = head->next;
ListNode *evenHead = even;
while(even && even->next){
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}Java
class Solution {
public ListNode oddEvenList(ListNode head){
if (head == null || head.next == null) return head;
ListNode odd = head, 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;
}
}复杂度
时间
O(n)
每个节点只被重接一次，整条扫一遍
空间
O(1)
只用 odd / even / evenHead 三个指针，原地改 next
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 奇偶链表 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么相对顺序能保持不变？+
奇链按原顺序依次接奇位置节点、偶链按原顺序依次接偶位置节点，两条线都没打乱内部次序，拼接也只是首尾相连。
能不能用一个额外数组先存奇位置再存偶位置？+
能，但那是 O(n) 额外空间；本解原地改 next 做到 O(1)，是面试要的最优。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 奇偶链表 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。