328. 奇偶链表
题目描述
输入一个单链表的头节点 head，链表用数组表示，例如 [1,2,3]。节点按位置从 1 开始编号：第 1 个节点算奇数位，第 2 个算偶数位，依次类推。注意这里看的是位置编号，与节点里存的值无关。
请重排链表：先依次放所有奇数位上的节点，再接上所有偶数位上的节点。每一组内部要保持节点在原链表中的先后顺序。
返回重排后链表的头节点。链表可以为空。要求只用 O(1) 的额外空间，时间复杂度为 O(n)。
示例 1
输入：head = [1,2,3,4,5] 输出：[1,3,5,2,4]
解释：奇数位节点是 1,3,5，偶数位节点是 2,4，前者在前，后者接在后面。
示例 2
输入：head = [2,1,3,5,6,4,7] 输出：[2,3,6,7,1,5,4]
解释：奇数位依次是 2,3,6,7，偶数位依次是 1,5,4，拼起来得到输出。
数据范围
n为链表节点数0 <= n <= 10^4-10^6 <= Node.val <= 10^6
解题思路
把一条链拆成两条：odd 串起奇数位节点，even 串起偶数位节点，并记住偶数链的头 even_head。每轮让 odd 跳过一个节点接到 even.next，再让 even 跳过一个节点接到 odd.next，两者交替前进。最后把奇数链的尾巴接到 even_head 上。
为什么正确
每轮开始时，odd 是奇数链的尾巴，even 是偶数链的尾巴，并且 odd.next == even，原链上还没处理的部分从 even.next 开始。
复杂度分析
时间 O(n)，每个节点只被重新链接一次；额外空间 O(1)，只用了几个指针。
易错点
一定要提前保存 even_head，因为循环过程中 even 一直在往后走，最后就找不到偶数链的头了。循环条件要写 even and even.next：节点数为奇数时，even 先变成 None；为偶数时，even.next 先变成 None。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
odd = head
even_head = even = head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return headclass Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null)
return head;
ListNode odd = head;
ListNode evenHead = head.next, even = evenHead;
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;
}
}class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head)
return head;
ListNode* odd = head;
ListNode* evenHead = head->next; ListNode* even = evenHead;
while (even && even->next) {
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 head
}
odd := head
evenHead := head.Next; even := evenHead
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
}var oddEvenList = function(head) {
if (!head)
return head;
let odd = head;
const evenHead = head.next; let even = evenHead;
while (even && even.next) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
};function oddEvenList(head: ListNode | null): ListNode | null {
if (!head)
return head;
let odd: ListNode = head;
const evenHead = head.next; let even = evenHead;
while (even && even.next) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}