leetcode328. 奇偶鏈表

給定單鏈表的頭節點 head ，將所有索引為奇數的節點和索引為偶數的節點分別組合在一起，然后返回重新排序的列表。
第一個節點的索引被認為是 奇數 ， 第二個節點的索引為 偶數 ，以此類推。
請注意，偶數組和奇數組內部的相對順序應該與輸入時保持一致。
你必須在 O(1) 的額外空間復雜度和 O(n) 的時間復雜度下解決這個問題。

示例 1:

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

示例 2:

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

算法的核心思想是通過兩個指針 odd 和 even 來分別遍歷奇數位和偶數位的節點，然后在遍歷的過程中逐步構建新的鏈表，使得奇數位的節點在偶數位的節點之前。

邊界條件檢查：首先，函數檢查 head 是否為 NULL。如果鏈表為空（即 head == NULL），則不需要進行任何操作，直接返回 head。

初始化指針：
ListNode* even = head->next; 初始化 even 指針指向第二個節點，即偶數位的第一個節點。
ListNode* odd = head; 初始化 odd 指針指向第一個節點，即奇數位的第一個節點。
ListNode* evenhead = even; 初始化 evenhead 指針，它將用于最后將偶數部分連接到奇數部分的末尾。

鏈表遍歷：使用 while 循環遍歷鏈表，直到 even 或 even->next 為 NULL，即到達鏈表的末尾或偶數位的最后一個節點。
在循環內部，首先將 odd->next 設置為 even->next，這樣 odd 節點就指向了下一個奇數位的節點。
然后將 odd 移動到下一個奇數位。
接著，將 even->next 設置為 odd->next，這樣 even 節點就指向了下一個偶數位的節點。
最后，將 even 移動到下一個偶數位。

連接偶數部分：當循環結束時，odd 指針將指向奇數部分的最后一個節點。此時，將 odd->next 設置為 evenhead，即將偶數部分連接到奇數部分的末尾。

返回結果：最后，函數返回 head，即重排后的鏈表的頭節點。

這個算法的時間復雜度是 O(N)，其中 N 是鏈表的長度。這是因為算法只需要遍歷鏈表一次。空間復雜度是 O(1)，因為除了輸入參數外，算法只使用了有限的額外空間（幾個指針變量）。
具體代碼如下：

class Solution {public:ListNode* oddEvenList(ListNode* head) {//如果鏈表為空，不用重排if (head == NULL)return head;//even開頭指向第二個節點，可能為空ListNode* even = head->next;//odd開頭指向第一個節點ListNode* odd = head;//指向even開頭ListNode* evenhead = even;while (even != NULL && even->next != NULL) {//odd連接even的后一個，即奇數位odd->next = even->next;//odd進入后一個奇數位odd = odd->next;//even連接后一個奇數的后一位，即偶數位even->next = odd->next;//even進入后一個偶數位even = even->next;}//even整體接在odd后面odd->next = evenhead;return head;}
};