題目網址：https://leetcode.cn/problems/odd-even-linked-list/

題意：給一 single linked list 的 head, 將奇數位置的 node 分組在一起, 然後是偶數位置的 node 分組在一起, 然後將偶數組 linked list 串接在奇數組 linked list 後面。

注意：奇數組和偶數組內的相對順序應和輸入中的順序相同。

設計 $O(n)$ time 且 $O(1)$ space 的演算法

Solution：

想法：用兩個奇偶 pointers 分別指向奇偶 linked list 的起始位置, 另外需要一個單獨的 pointer evenHead 來保存偶數組 linked list 的起點位置

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        ListNode *evenHead = head->next;
        ListNode *odd = head, *even = evenHead;

        // 判斷是否有偶奇節點
        while (odd->next && even->next) {
            odd->next = odd->next->next;
            odd = odd->next;
            even->next = even->next->next;
            even = even->next;
        }

        odd->next = evenHead;

        return head;
    }
};
  • time：$O(n)$ ➔ 遍歷整個 linked list
  • space：$O(1)$ ➔ 只需常數空間