Partition List Problem


Description

LeetCode Problem 86.

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.

Example 1:

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

Example 2:

1
2
Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

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


Sample C++ Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == NULL)
            return NULL;
        ListNode* head_l = NULL;
        ListNode* head_ge = NULL;
        ListNode* curr_l;
        ListNode* curr_ge;
        
        ListNode* curr = head;
        while (curr != NULL) {
            if (curr->val < x) {
                if (head_l == NULL) {
                    head_l = curr;
                    curr_l = curr;
                } else {
                    curr_l->next = curr;
                    curr_l = curr_l->next;
                }
            } else {
                if (head_ge == NULL) {
                    head_ge = curr;
                    curr_ge = curr;
                } else {
                    curr_ge->next = curr;
                    curr_ge = curr_ge->next;
                }
            }
            curr = curr->next;
        }

        if (head_l == NULL) {
            curr_ge->next = NULL;
            return head_ge;
        } else if (head_ge == NULL) {
            curr_l->next = NULL;
            return head_l;
        }
        else {
            curr_l->next = head_ge;
            curr_ge->next = NULL;
            return head_l;
        }
        
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...