LeetCode Algorithm 86. Separate linked list

Topic link ：86. Separate the list

Ideas

Algorithm ： simulation
data structure ： Linked list
Ideas ：（ At first, I tried to exchange in place with a bunch of pointers , I successfully dizzy myself and then opened the question .）
First, create two virtual nodes , It is respectively used to maintain the requirements in the topic less than x Node sum of is greater than x The node of , Then iterate through the list , When you encounter a node, you can judge what type it is , Then put it behind the corresponding virtual node .

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;
    }
};