LeetCode 328 Odd Even Linked List（奇偶鏈表）（*）

翻譯

給定一個單鏈表，將所有的奇節點歸為一組，偶節點緊隨其後。

請注意我們現在談的是奇節點而不是節點上的值。

你應該嘗試就地完成。

程序應該在O(1)空間復雜度和O(nodes)時間復雜度下完成。

例如：
給定 1->2->3->4->5->NULL，
返回 1->3->5->2->4->NULL。

注釋：
最後歸類出來的奇節點和偶節點的相對位置應該和輸入時一致。

第一個節點為奇節點，第二個節點為偶節點，以此類推……

原文

Given a singly linked list, group all odd nodes together followed by the even nodes. 

Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. 

The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:

The relative order inside both the even and odd groups should remain as it was in the input. 

The first node is considered odd, the second node even and so on ...

分析

寒假第一題，農村老家真的超冷……我想的思路可能不是太簡潔，再加上考慮的不全面，導致不斷的出錯、調試、出錯、調試……最終花了好久才完成，而代碼已經談不上簡潔了。

ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head;
    bool oddFlag = true;          
    ListNode* odd = head;
    ListNode* even = head->next;
    ListNode* oddHead = odd;
    ListNode* evenHead = even;
    head = head->next->next;      
    while (head) {
        if (oddFlag) {
            odd->next = head;
            odd = odd->next;
            oddFlag = false;
        }
        else {
            even->next = head;
            even = even->next;
            oddFlag = true;
        }
        head = head->next;
    }
    if (!oddFlag)
        even->next = NULL;
    odd->next = evenHead; 
    return oddHead;
}

過程叻大概是這樣的：

1，判斷是否為空，兩種情況都返回head。
2，新建odd和even來不斷遍歷，和head一樣，它們三個是會移動的。
3，oddHead和evenHead是不會動的，用於最後拼湊新的鏈表。
4，用isOdd來判斷當前的節點是否是奇節點，不管是不是，它們的操作都是類似的。
5，最後的時候，如果是奇節點結尾的，那麼可能偶節點最後一個會是多余的，所以需要將它干掉。
6，拼湊新的鏈表用於返回。

然而仔細想想呢，其實還有很大的改善空間，比如說：

既定義了oddHead還定義了evenHead，有一個很好的解決方案是：用head來作為oddHead。這樣在返回的時候我們就可以直接返回head了，那麼新的問題來了？之前我們是用的head來進行迭代的，那麼現在呢？我們需要找到一種新的解決辦法。

我們來回顧一下之前的算法：用head來遍歷每一個節點，用一個bool變量來標志這個節點的性質（奇節點還是偶節點）。舉個例子：

1，2，3，4，5，NULL

我們發現奇節點的下一個節點恰好就是偶節點的下一個節點（1的下一個節點應該是2的下一個節點，也就是3），而偶節點的下一個節點也恰好是奇節點是下一個節點。這樣我們就可以只通過odd和even兩個變量來遍歷了，既省去了用來遍歷的head，也省去了一個變量oddHead，同時還可以直接返回head，何樂而不為呢？

還記得上面我們用了這樣一步嗎？

if (!isOdd)
    even->next = NULL;
odd->next = evenHead; 

如果按照現在的思路，那麼也完全不需要這個判斷了，因為在求next的過程中，已經將該用NULL的地方設置成了NULL。

所以代碼修改成：

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;
}

while循環中間的部分的順序可不能顛倒了，只有更新了odd之後，才能將odd->next的設為even->next。

代碼

/**
* 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;
    }
};