Odd Even Linked List

題目描述

給定一個 Linked List，將所有奇數位置的節點排在偶數位置節點前面。要求 O(1) 空間、O(n) 時間，且保持相對順序。

輸入: [1,2,3,4,5]
輸出: [1,3,5,2,4]

輸入: [2,1,3,5,6,4,7]
輸出: [2,3,6,7,1,5,4]

解題思路

初始化指針

odd 指向 head（第 1 個）、even 指向 head.next（第 2 個）、evenHead 保存偶數鏈起點

交替串接

odd.next = even.next 讓奇數節點跳過偶數指向下一個奇數；even.next = odd.next 同理

移動指針

odd = odd.next 前進到新的奇數節點、even = even.next 前進到新的偶數節點

合併

迴圈結束後執行 odd.next = evenHead，把整條偶數鏈接到奇數鏈尾端

程式碼

C#

csharp

public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if (head == null) return null;
 
        var odd = head;
        var even = head.next;
        var 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;
    }
}

TypeScript

typescript

function oddEvenList(head: ListNode | null): ListNode | null {
    if (!head) return null;
 
    let odd = head;
    let even = head.next;
    const 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;
}

Python

python

def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return None
 
    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 head

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |

Time 為 O(n) 是因為 odd 和 even 各自走過一半的節點，合計遍歷 n 個節點恰好一次。Space 為 O(1) 是因為只用了 odd、even、evenHead 三個指針，在原鏈表上直接修改。

邊界情況

空鏈表或單一節點：直接回傳，不需要任何處理
只有兩個節點：[1,2] 奇數鏈為 [1]、偶數鏈為 [2]，合併後 [1,2] 不變
奇數長度：如 [1,2,3]，迴圈結束時 even 為 null，odd 指向最後一個奇數節點 3

圖解

1 (奇)

奇數鏈→

2 (偶)

偶數鏈→

3 (奇)

奇數鏈→

4 (偶)

→

5 (奇)

合併→

1→3→5→2→4

圖表展示了奇偶分離的核心邏輯：奇數位 1、3、5 串成一條鏈，偶數位 2、4 串成另一條，最後 5 的 next 指向偶數鏈頭 2，形成最終結果 1→3→5→2→4。

進階觀點

💡面試追問

Q: 為什麼迴圈條件是 even != null && even.next != null？ A: even 永遠在 odd 後面一個位置。如果 even 為 null，代表鏈表長度為奇數且已處理完；如果 even.next 為 null，代表 even 是最後一個節點，沒有下一個奇數節點可處理。兩種情況都該停止。

Q: 忘記保存 evenHead 會怎樣？ A: 迴圈中 even 指針會不斷前進到偶數鏈末尾。如果沒有 evenHead，迴圈結束後無法找到偶數鏈的起點，導致偶數鏈完全丟失，odd.next 無法正確連接。

變體題：LC 86 Partition List（按值分割）、LC 725 Split Linked List in Parts。

理解測驗

🤔 為什麼要用 evenHead 變數？

🤔 [1,2,3] 經過處理後的結果是？