LeetCode Algorithm 86. 分隔鏈錶

題目鏈接：86. 分隔鏈錶

Ideas

算法：模擬
數據結構：鏈錶
思路：（我一開始竟然妄圖用一堆指針進行原地交換，成功把自己繞暈然後打開了題解。）
首先還是創建兩個虛擬節點，分別用來維護題目中要求的小於x的節點和大於x的節點，然後遍曆鏈錶，遇到一個節點就判斷是什麼類型，然後把它歸到相應的虛擬節點後面即可。

Code

C++

class Solution {
    
public:
    ListNode* partition(ListNode* head, int x) {
    
        ListNode *small = new ListNode(0), *large = new ListNode(0);
        ListNode *smallHead = small, *largeHead = large;
        while (head != nullptr) {
    
            if (head->val < x) {
    
                small->next = head;
                small = small->next;
            } else {
    
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = nullptr;
        small->next = largeHead->next;
        return smallHead->next;
    }
};