📘 題目敘述
給定一個單向鏈結串列 head，請將所有位於奇數位置的節點放在前面，所有位於偶數位置的節點放在後面，並回傳重新排列後的鏈結串列。
這裡的「奇數 / 偶數」指的是節點在鏈結串列中的位置（1-indexed），而不是節點的值。
請注意：奇數節點與偶數節點內部的相對順序要保持不變。
條件限制
- 節點數量範圍為
[0, 10^4]。 -10^6 ≤ Node.val ≤ 10^6。
🧠 解題思路（一）建立dummy
我的做法是「分兩次掃描原本的 linked list」，把結果依序接到一條新的 linked list 上：
- 先走奇數位置：
head (第1個) -> 第3個 -> 第5個 -> ... - 再走偶數位置：
head->next (第2個) -> 第4個 -> 第6個 -> ...
每走到一個節點，我就把它的值 val 用 new ListNode(...) 建一個新節點，接到結果串列的尾端。
這樣做可以很直觀地達到：
- 奇數位置全部先接完
- 偶數位置再接在後面
- 並且保持原本的相對順序
所有變數
head：輸入鏈結串列的頭節點dummy：結果鏈結串列的虛擬頭（方便接節點，不用特判第一個）tail：結果鏈結串列的尾巴指標（每次都把新節點接在尾巴後面）h：用來掃描原鏈結串列的指標（第一次掃奇數位置，第二次掃偶數位置）
🪜 主要流程步驟
1. 前置判斷：長度太短直接回傳
if (!head || !(head->next)) {
return head;
}- 如果
head == nullptr：空串列。 - 或
head->next == nullptr：只有一個節點。這兩種情況本來就已經符合題意，不需要重排。
2. 建立結果串列的起點（dummy + tail）
ListNode dummy(0);
ListNode* tail = &dummy;dummy是一個不重要的節點（值是 0 只是佔位）。- 真正答案會從
dummy.next開始。 tail一開始指向dummy，代表結果串列目前是空的。
3. 第一段 while：掃「奇數位置」節點並接到結果
ListNode* h = head;
while (h) {
tail->next = new ListNode(h->val);
tail = tail->next;
if (h->next) {
h = h->next->next;
} else {
break;
}
}這段的意思是：
h從head開始（第 1 個節點，奇數位置）。- 每次把
h->val複製成新節點接到結果尾端。 - 然後
h嘗試跳兩步h = h->next->next，這樣就會走到下一個奇數位置（1→3→5→...）。
為什麼要 if (h->next)？
- 因為要跳兩步之前，至少要確保
h->next存在。 - 否則
h->next->next會出錯。
4. 第二段 while：掃「偶數位置」節點並接到結果尾端
h = head->next;
while (h) {
tail->next = new ListNode(h->val);
tail = tail->next;
if (h->next) {
h = h->next->next;
} else {
break;
}
}這段跟上一段完全一樣，只是起點變成 head->next（第 2 個節點，偶數位置）。
所以會走：第2個 → 第4個 → 第6個 → ...，最後就把偶數位置節點全部接在奇數位置後面。
5. 回傳答案
return dummy.next;因為 dummy 只是虛擬頭，真正串列的頭是 dummy.next。
💻 程式碼實作（一）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !(head->next)) {
return head;
}
ListNode dummy(0);
ListNode* tail = &dummy;
ListNode* h = head;
while (h) {
tail->next = new ListNode(h->val);
tail = tail->next;
if (h->next) {
h = h->next->next;
} else {
break;
}
}
h = head->next;
while (h) {
tail->next = new ListNode(h->val);
tail = tail->next;
if (h->next) {
h = h->next->next;
} else {
break;
}
}
return dummy.next;
}
};🧠 解題思路（二）奇偶指標
我這份寫法是「把原串列拆成兩條鏈，再接起來」，全程只改 next 指標，不建新節點。
核心想法：
odd指向目前「奇數鏈」最後一個節點。even指向目前「偶數鏈」最後一個節點。ehead保留偶數鏈的頭（原本的第二個節點），最後要把它接回奇數鏈尾端。
重點是：每次都把下一個奇數節點接到 odd 後面，再把下一個偶數節點接到 even 後面，這樣相對順序就會自然保持原樣。
所有變數
head：輸入 linked list 的頭節點，也是最後回傳的頭。odd：目前奇數鏈的尾巴指標（一路往後推進）。even：目前偶數鏈的尾巴指標（一路往後推進）。ehead：偶數鏈的頭指標（用來在最後接回去）。
🪜 主要流程步驟
1. 特例：長度 0 或 1 直接回傳
- 如果
!head或!head->next，代表節點不夠分奇偶，原樣回傳即可。
2. 初始化奇偶兩條鏈的起點
odd = head：第一個節點（奇數）。even = head->next：第二個節點（偶數）。ehead = even：記住偶數鏈的頭，最後要接回去。
3. 交替重接指標，把奇數節點串成一條、偶數節點串成一條
迴圈條件用 while (even && even->next)，因為要把「下一個奇數節點」接到 odd 後面，這個節點就是 even->next，所以 even->next 必須存在。
每一輪做兩次接法：
- 接奇數鏈：
odd->next = even->next，再odd = odd->next（odd 往前走到新的尾巴）。 - 接偶數鏈：
even->next = odd->next，再even = even->next（even 往前走到新的尾巴）。
4. 把偶數鏈接到奇數鏈尾端
- 迴圈結束後，奇數鏈已經在前面串好了。
odd->next = ehead把偶數鏈整條接到後面。
5. 回傳 head
- 因為是原地改指標，頭不變，回傳
head。
💻 程式碼實作（二）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* odd = head; // 奇數
ListNode* even = head->next; // 偶數
ListNode* ehead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = ehead;
return head;
}
};🔗 題目連結
https://leetcode.com/problems/odd-even-linked-list/