# 【LeetCode】 328. Odd Even Linked List

## Description
> Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
> The first node is considered odd, and the second node is even, and so on.
> Note that the relative order inside both the even and odd groups should remain as it was in the input.
> You must solve the problem in O(1) extra space complexity and O(n) time complexity.

> Constraints:
The number of nodes in the linked list is in the range [0, 10^4].
-10^6 <= Node.val <= 10^6

> 給予一個單向串列陣列的開頭，將全部索引為奇數的節點當作一組，然後偶數節點緊跟在後，並回傳重新排序過後的結果。
> 第一個節點被視為奇數，第二個為偶數，以此類推。
> 注意奇數與偶數組內相對的順序應該保持與輸入時相同。
> 你應該在 O(1) 的額外空間複雜度與 O(n) 的時間複雜度中完成這道題目。

> 限制：
> 節點的總數在 [0, 10^4] 之中
> -10^6 <= 節點的值 <= 10^6

## Example:


Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]


Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

## Solution

* 這道題目要硬寫的話不難，但考慮到複雜度限制的部分就會變得有些困難
* 空間複雜度 O(1)，表示我們不能再開一個 Linked-List 去儲存資料(例如你可能會想要開一個空間先放偶數組等等)
* 時間複雜度 O(n)，表示我們不能用類似巢狀的結構去掃這個 List
* 這代表我們必須在一層的 for 之中就把奇數與偶數漂亮的切開
* 我們需要做的事情概念上很簡單
* 將一個指標從開頭每次往後兩步，去遍歷每一個奇數節點
* 每次遍歷節點的時候，將該節點移至前方
* 為此，你可能需要在一個節點去記錄他應該要放在哪裡
* 思路清晰之後就是實作的部分，要注意將 Node 重新放入時，前後的 next 要指向對的位置

### Code

/**
 * 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 *pre = head, *cur = head->next;
        // pre: where the odd node should insert
        // cur: which node we handle now
        while (cur && cur->next) {
            ListNode *tmp = pre->next;
            pre->next = cur->next;
            cur->next = cur->next->next;
            pre->next->next = tmp;
            cur = cur->next;
            pre = pre->next;
        }
        return head;
    }
};

###### tags: `LeetCode` `C++`