86. separate linked list

Title Description

Give you a list of the head node head And a specific value x , Please separate the linked list , Make all Less than x All of the nodes appear in Greater than or equal to x Before the node .

You should Retain The initial relative position of each node in the two partitions .

 Example  1：
 Input ：head = [1,4,3,2,5,2], x = 3
 Output ：[1,2,2,4,3,5]

 Example  2：
 Input ：head = [2,1], x = 2
 Output ：[1,2]

 Tips ：

 The number of nodes in the linked list is in the range  [0, 200]  Inside 
-100 <= Node.val <= 100
-200 <= x <= 200

Answer key （C++）

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