LeetCode 328 奇偶鏈表：原地重組奇偶節點 O(1) 空間

題目描述

給定單鏈表，將所有奇數位置節點（第 1、3、5... 個）移至前部，偶數位置節點移至後部。要求：

• 原地操作，O(1) 空間
• O(n) 時間
• 保持奇節點間、偶節點間相對順序

範例：

輸入: 1→2→3→4→5→NULL
輸出: 1→3→5→2→4→NULL

解題思路：雙指針原地編織

關鍵洞察：奇節點的下一個是偶節點的下一個（即下一個奇節點），偶節點的下一個是奇節點的下一個（即下一個偶節點）。

維護兩條鏈：

• odd 指向奇鏈尾，even 指向偶鏈尾
• evenHead 記住偶鏈頭，最後連接

迭代邏輯：

odd->next = even->next;  // 奇接下一奇
odd = odd->next;
even->next = odd->next;  // 偶接下一偶
even = even->next;

循環條件：odd->next && even->next（確保都有下一個）

C++ 參考實現（優化版）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        
        while (odd->next && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        
        odd->next = evenHead;
        return head;
    }
};

從朴素版到優化版的演進

朴素版：用 head 遍歷 + bool isOdd 判斷 + 額外 oddHead，邏輯繁雜，需處理尾部 NULL 收尾。

優化洞察：

1. head 即為 oddHead，無需額外變量
2. 奇偶節點 next 互為對方 next，無需 head 遍歷，直接用 odd/even 推進
3. 循環內賦值順序固定：先更新 odd->next，再用新 odd 更新 even->next
4. 天然處理尾部 NULL，無需額外收尾判斷

核心要點總結

• 原地編織：不創建新節點，僅修改 next 指針
• 雙指針推進：odd、even 同步前進，利用 next 互指特性
• 頭節點複用：head 直接作為奇鏈頭，返回簡潔
• 邊界自處理：循環條件與賦值順序天然處理奇/偶長度差異

奇偶鏈表是鏈表指針操作的精練練習，從「用標記位遍歷」進化到「雙指針互推」體現了演算法優化的思維深度。