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.
What is the space complexity of the following code?
1int sum(int n) {
2 if (n <= 0) {
3 return 0;
4 }
5 return n + sum(n - 1);
6}
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 settingt1.nextto the current node, and then advancingt1tot1.next. - If the value is greater than or equal to
x, we move the node to the end of the "greater" list, executed by settingt2.nextto the current node, and then advancingt2tot2.next. - In both cases, after moving the node, we advance
headtohead.nextto 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
t1andt2that 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
d1andd2, we avoid having to write special case code for when the heads of the "smaller" or "greater" lists areNone.
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.
Which of the following is a good use case for backtracking?
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:
1Linked 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.
1d1 -> None
2d2 -> None
3t1 -> d1
4t2 -> d2
Now we iterate over the original list with the help of head pointer:
headpoints to1, which is less than3, so we attachheadto the "smaller" list and movet1.1smaller list: d1 -> 1 2greater list: d2 -> None 3t1 now points to 1 4t2 still points to d2headnow points to4, which is greater than or equal to3, so we attachheadto the "greater" list and movet2.1smaller list: d1 -> 1 2greater list: d2 -> 4 3t1 still points to 1 4t2 now points to 4headnow points to3, which is equal to3, soheadis attached to the "greater" list andt2is moved.1smaller list: d1 -> 1 2greater list: d2 -> 4 -> 3 3t1 still points to 1 4t2 now points to 3headnow points to2, which is less than3, soheadis attached to the "smaller" list andt1is moved.1smaller list: d1 -> 1 -> 2 2greater list: d2 -> 4 -> 3 3t1 now points to 2 4t2 still points to 3- Finally,
headpoints to5, which is greater than3, soheadis attached to the "greater" list andt2is moved.1smaller list: d1 -> 1 -> 2 2greater list: d2 -> 4 -> 3 -> 5 3t1 still points to 2 4t2 now points to 5
After iterating through the entire list, we connect the "smaller" list to the "greater" list:
t1.next(which is2.next) is set tod2.next(which is4), merging the lists.t2.next(which is5.next) is set toNone, indicating the end of the linked list.
The final merged list, omitting the dummy node d1, is:
11 -> 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
361// 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}
521/**
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};
531// 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};
52Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.