【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++