86. Partition List

Problem Description

The problem presents us with a singly linked list and a value x. Our task is to rearrange the nodes in the linked list in such a way that all nodes having values less than x are placed before the nodes with values greater than or equal to x. Importantly, we need to maintain the original relative order of the nodes that are less than x and those that are greater than or equal to x.

Intuition

The primary intuition for solving this problem is to create two separate linked lists:

The first for nodes with values less than x (we'll call this list "smaller").
The second for nodes with values greater than or equal to x (we'll call this list "greater").

As we iterate through the original list, we evaluate each node's value. If a node's value is less than x, we append it to the "smaller" list. If a node's value is greater than or equal to x, we append it to the "greater" list. After iterating through the whole list, we connect the end of the "smaller" list to the beginning of the "greater" list to form the final reordered linked list. This approach ensures that the original relative ordering is preserved within each partition.

It is important to be careful with edge cases, such as when the linked list has no nodes or all nodes are smaller or larger than x. However, the approach will correctly handle these scenarios as the lists will simply be empty or one of them will not be used.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

In the given solution approach, we use two dummy nodes d1 and d2 as the heads of the two new lists: one for elements less than x (the "smaller" list) and one for elements greater than or equal to x (the "greater" list). Using these dummy nodes allows us to append to these lists without having to check if they are empty.

We then iterate through the original linked list with the following steps:

We check the value of the current node pointed to by head.
If the value is less than x, we move the node to the end of the "smaller" list, done by setting t1.next to the current node, and then advancing t1 to t1.next.
If the value is greater than or equal to x, we move the node to the end of the "greater" list, executed by setting t2.next to the current node, and then advancing t2 to t2.next.
In both cases, after moving the node, we advance head to head.next to continue to the next node in the list.

Once we finish iterating through the entire list, we merge the two lists. We set the next pointer of the tail of the "smaller" list (t1.next) to the head of the "greater" list (d2.next). It is crucial then to set the next of the last node in the "greater" list to None to indicate the end of the linked list.

This partitioning keeps the nodes in their original relative order within the two partitions because nodes are moved individually and the next pointers of the original list are preserved. The code concludes by returning d1.next, which is the head of the merged, partitioned list (excluding the dummy head d1).

This approach uses the following patterns:

Two Pointer Technique: Having separate pointers t1 and t2 that keep track of the current end of the "smaller" and "greater" lists, respectively, allows us to efficiently append to these lists.
Sentinel Node (Dummy Node): By using dummy head nodes d1 and d2, we avoid having to write special case code for when the heads of the "smaller" or "greater" lists are None.

In essence, the algorithm separates and then recombines the linked list's nodes based on their values in relation to x, while maintaining their original relative order.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we are given the following linked list and the value x = 3:

Linked List: 1 -> 4 -> 3 -> 2 -> 5

Our task is to rearrange this list so that all nodes with values less than 3 are before nodes with values greater than or equal to 3, while maintaining their original relative order.

We start by initiating two dummy nodes, d1 and d2, which will serve as the heads of our "smaller" and "greater" lists. We also have two pointers t1 and t2 that start at these dummy nodes respectively.

d1 -> None
d2 -> None
t1 -> d1
t2 -> d2

Now we iterate over the original list with the help of head pointer:

head points to 1, which is less than 3, so we attach head to the "smaller" list and move t1.

smaller list: d1 -> 1
greater list: d2 -> None
t1 now points to 1
t2 still points to d2

head now points to 4, which is greater than or equal to 3, so we attach head to the "greater" list and move t2.

smaller list: d1 -> 1
greater list: d2 -> 4
t1 still points to 1
t2 now points to 4

head now points to 3, which is equal to 3, so head is attached to the "greater" list and t2 is moved.

smaller list: d1 -> 1
greater list: d2 -> 4 -> 3
t1 still points to 1
t2 now points to 3

head now points to 2, which is less than 3, so head is attached to the "smaller" list and t1 is moved.

smaller list: d1 -> 1 -> 2
greater list: d2 -> 4 -> 3
t1 now points to 2
t2 still points to 3

Finally, head points to 5, which is greater than 3, so head is attached to the "greater" list and t2 is moved.

smaller list: d1 -> 1 -> 2
greater list: d2 -> 4 -> 3 -> 5
t1 still points to 2
t2 now points to 5

After iterating through the entire list, we connect the "smaller" list to the "greater" list:

t1.next (which is 2.next) is set to d2.next (which is 4), merging the lists.
t2.next (which is 5.next) is set to None, indicating the end of the linked list.

The final merged list, omitting the dummy node d1, is:

1 -> 2 -> 4 -> 3 -> 5

This is the reordered list where nodes with values less than 3 are placed before nodes with values greater than or equal to 3, and their relative order is maintained as per the problem requirement.

Solution Implementation

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6class Solution:
7    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
8        # Dummy nodes to start the lists for elements less than x and not less than x
9        less_head = ListNode() 
10        not_less_head = ListNode()
11      
12        # Tail pointers for each list, which will help in appending new nodes
13        less_tail = less_head
14        not_less_tail = not_less_head
15
16        # Traverse the original list
17        while head:
18            # If the current value is less than x, append it to the list of less_tail
19            if head.val < x:
20                less_tail.next = head
21                less_tail = less_tail.next
22            # If the current value is not less than x, append it to the list of not_less_tail
23            else:
24                not_less_tail.next = head
25                not_less_tail = not_less_tail.next
26            # Move to the next node in the original list
27            head = head.next
28
29        # Connect the two lists together
30        less_tail.next = not_less_head.next
31        # The last node of the new list should point to None to indicate the end of the list
32        not_less_tail.next = None
33      
34        # Return the head of the list with nodes less than x followed by nodes not less than x
35        return less_head.next
36

1// Definition for singly-linked list.
2class ListNode {
3    int val;
4    ListNode next;
5
6    // Constructor to initialize the node with a value.
7    ListNode() {}
8  
9    // Constructor to initialize the node with a value and a reference to the next node.
10    ListNode(int val) {
11        this.val = val;
12    }
13
14    // Constructor to initialize the node with a value and a reference to the next node.
15    ListNode(int val, ListNode next) {
16        this.val = val;
17        this.next = next;
18    }
19}
20
21class Solution {
22  
23    // This method partitions a linked list around a value x, such that all nodes less than x come before nodes greater than or equal to x.
24    public ListNode partition(ListNode head, int x) {
25        ListNode lessHead = new ListNode(0); // Dummy node for the 'less' sublist.
26        ListNode greaterHead = new ListNode(0); // Dummy node for the 'greater' sublist.
27        ListNode lessTail = lessHead; // Tail pointer for the 'less' sublist.
28        ListNode greaterTail = greaterHead; // Tail pointer for the 'greater' sublist.
29
30        // Iterate over the original list and divide the nodes into 'less' and 'greater' sublists.
31        while (head != null) {
32            if (head.val < x) {
33                // Append to 'less' sublist.
34                lessTail.next = head;
35                lessTail = head;
36            } else {
37                // Append to 'greater' sublist.
38                greaterTail.next = head;
39                greaterTail = head;
40            }
41            head = head.next; // Move to the next node in the original list.
42        }
43
44        // Connect the 'less' sublist with the 'greater' sublist.
45        lessTail.next = greaterHead.next;
46        greaterTail.next = null; // Ensure the last node of 'greater' sublist points to null.
47
48        // Return the head of the 'less' sublist, which now contains all nodes in the partitioned order.
49        return lessHead.next;
50    }
51}
52

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int value;
5 *     ListNode *next;
6 *     ListNode() : value(0), next(nullptr) {}
7 *     ListNode(int x) : value(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : value(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* partition(ListNode* head, int x) {
14        // Create two dummy head nodes for the two partitions
15        ListNode* lessHead = new ListNode(); // Head of the list for elements < x
16        ListNode* greaterHead = new ListNode(); // Head of the list for elements >= x
17
18        // Use two pointers to keep track of the current end of the two partitions
19        ListNode* lessTail = lessHead; // Tail of the list for elements < x
20        ListNode* greaterTail = greaterHead; // Tail of the list for elements >= x
21
22        // Iterate through the original list and separate nodes into the two partitions
23        while (head) {
24            if (head->value < x) {
25                // Append to the less-than partition
26                lessTail->next = head;
27                lessTail = lessTail->next;
28            } else {
29                // Append to the greater-or-equal partition
30                greaterTail->next = head;
31                greaterTail = greaterTail->next;
32            }
33            // Move to the next node in the original list
34            head = head->next;
35        }
36
37        // Connect the two partitions
38        lessTail->next = greaterHead->next;
39      
40        // Ensure the end of the greater-or-equal partition is null
41        greaterTail->next = nullptr;
42
43        // The start of the less-than partition is the new head of the modified list
44        ListNode* newHead = lessHead->next;
45
46        // Clean up the dummy head nodes
47        delete lessHead;
48        delete greaterHead;
49
50        return newHead;
51    }
52};
53

1// ListNode class definition for TypeScript
2class ListNode {
3    val: number;
4    next: ListNode | null;
5
6    constructor(val: number = 0, next: ListNode | null = null) {
7        this.val = val;
8        this.next = next;
9    }
10}
11
12/**
13 * Partition a linked list around a value x, such that all nodes less than x come
14 * before nodes greater than or equal to x.
15 * @param {ListNode | null} head - The head of the input linked list.
16 * @param {number} x - The partition value, where elements are repositioned around.
17 * @return {ListNode | null} - The head of the modified linked list.
18 */
19const partition = (head: ListNode | null, x: number): ListNode | null => {
20    // Two dummy nodes to start the less and greater sublist
21    const lessDummy: ListNode = new ListNode();
22    const greaterDummy: ListNode = new ListNode();
23
24    // Two pointers to track the current end node of the sublists
25    let lessTail: ListNode = lessDummy;
26    let greaterTail: ListNode = greaterDummy;
27
28    // Iterate through the linked list and partition the nodes
29    while (head) {
30        if (head.val < x) {
31            // If current node value is less than x, add it to the less sublist
32            lessTail.next = head;
33            lessTail = lessTail.next;
34        } else {
35            // If current node value is greater or equal to x, add it to the greater sublist
36            greaterTail.next = head;
37            greaterTail = greaterTail.next;
38        }
39        // Move to the next node in the list
40        head = head.next;
41    }
42
43    // Connect the end of the less sublist to the beginning of the greater sublist
44    lessTail.next = greaterDummy.next;
45
46    // The last node of the greater sublist should point to null to end the list
47    greaterTail.next = null;
48
49    // Return the head of the less sublist, since it is now the head of the partitioned list
50    return lessDummy.next;
51};
52

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the linked list. This is because the code iterates through all the nodes exactly once, performing a constant amount of work for each node by checking the value and rearranging the pointers.

Space Complexity

The space complexity of the code is O(1). Despite creating two dummy nodes (d1 and d2) and two tail pointers (t1 and t2), the amount of extra space used does not scale with the size of the input (the number of nodes n); rather, it remains constant. The rearrangement of the nodes is done in place without allocating any additional nodes.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know