LeetCode 86. Partition List [Medium] [C++] 解題筆記

這題給定一個 Linked List 與一個 target value x，要求我們把 list 中小於 x 的 node 都排到大於等於 x的 node 前面去，小於 x 與大於等於 x 的 node 之間的相對順序要維持原樣。

EX:

        head = 1->4->3->2->5->2, x = 3

        Ans:  1->2->2->4->3->5

想法:

        這題基本上沒啥特別的技巧，就是實作題，首先先traverse 整個 list ，找到第一個

大於等於 x 的 node 當 pivot，之後只要遇到小於 x 的 node 就把它丟到 pivot 前，比較

需要注意的是 list 類的題目都要小心 head 的情況，因此簡單的實作方式是多新增一個

dummy node 來放在 head 之前，就可以很簡單的考慮 head 的情況拉。

Time Complexity: O(n) time

完整程式碼:

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* cur = head;
        ListNode* pre = &dummy;
        ListNode* less = &dummy;
        ListNode* pivot = nullptr;
        while (cur != nullptr) {
            if (cur->val >= x) {
                if (pivot == nullptr) {
                    pivot = cur;
                    less = pre;
                }   
                pre = cur;
                cur = cur->next;
            }
            else if (cur->val < x) {
                if (pivot != nullptr) {
                    auto tmp = less->next;
                    pre->next = cur->next;
                    less->next = cur;
                    less = less->next;
                    less->next = tmp;
                    cur = pre->next;
                }
                else {
                    pre = cur;
                    cur = cur->next;
                }
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }
        return dummy.next;
    }
};