WEI-CHENG CHEN

說明

給定一個 linklist 跟一個特定值 x，請你對 linklist 進行區分

使得所有小於 x 的 node，都要出現在 x 前面

解法

這題的解法就是將原本的 linklist 判斷並拆成兩個 linklist，最後再組起來

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(0);
        ListNode* smallHead = small;
        ListNode* large  = new ListNode(0);
        ListNode* largeHead = large;

        while(head){
            if(head->val<x){
                smallHead->next = head;
                smallHead = smallHead->next;
                head = head->next;
            }else{
                largeHead->next = head;
                largeHead = largeHead->next;
                head = head->next;
            }
        }

        // 兩個linklist合併
        smallHead->next = large->next;
        largeHead->next = nullptr;
        return small->next;
    }
};