86. Partition List

2020, Dec 05 One min read

1. Description

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.

2. Example

Example 1

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]

3. Constraints

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

4. Solutions

Two Pointers

n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode less_dummy;
        ListNode greater_equal_dummy;

        ListNode *less_tail = &less_dummy;
        ListNode *greater_equal_tail = &greater_equal_dummy;

        while (head != nullptr) {
            if (head->val < x) {
                less_tail->next = head;
                less_tail = head;
            } else {
                greater_equal_tail->next = head;
                greater_equal_tail = head;
            }

            head = head->next;
        }

        greater_equal_tail->next = nullptr;
        less_tail->next = greater_equal_dummy.next;

        return less_dummy.next;
    }
};

Search

Tags