grid47 Exploring patterns and algorithms
Oct 29, 2024
6 min read
Solution to LeetCode 86: Partition List Problem
Given the head of a linked list and a value x, partition the list such that all nodes with values less than x appear before nodes with values greater than or equal to x. The relative order of the nodes in each partition should be preserved.
Problem
Approach
Steps
Complexity
Input: The input consists of the head of a singly linked list and an integer x. The linked list contains nodes with integer values.
Example: Input: head = [6,2,5,3,8,1], x = 5
Constraints:
• The number of nodes in the list is between 0 and 200.
• -100 <= Node.val <= 100
• -200 <= x <= 200
Output: The output should return the head of the partitioned linked list, where nodes less than x appear first, followed by nodes greater than or equal to x. The relative order of nodes in each partition should be preserved.
Example: Output: [2,3,1,6,5,8]
Constraints:
• The list should maintain the relative order of elements within each partition.
Goal: To partition the linked list around the given value x such that all nodes with values less than x come before those with values greater than or equal to x, preserving the original order of the nodes.
Steps:
• Create two separate lists: one for values less than x, and one for values greater than or equal to x.
• Traverse the original list, and for each node, append it to the appropriate list based on its value.
• Once the traversal is complete, merge the two lists by connecting the last node of the first list to the head of the second list.
Goal: The solution must be efficient enough to handle up to 200 nodes in the linked list.
Steps:
• The number of nodes in the list is between 0 and 200.
• Node values range from -100 to 100.
• The integer x lies between -200 and 200.
Assumptions:
• The input list will always be a valid linked list with the specified range of values.
• The partitioning will maintain the relative order of nodes within each partition.
• Input: Input: head = [6,2,5,3,8,1], x = 5
• Explanation: The list is partitioned into nodes less than 5 (2, 3, 1) and nodes greater than or equal to 5 (6, 5, 8), maintaining their relative order.
• Input: Input: head = [4, 2, 7, 3], x = 5
• Explanation: Nodes less than 5 (4, 2, 3) appear first, followed by nodes greater than or equal to 5 (7). The relative order of each partition is preserved.
Approach: To solve the problem, we create two separate linked lists: one for nodes with values less than x, and one for nodes with values greater than or equal to x. After traversing the input list, we merge these two lists together to form the final partitioned list.
Observations:
• We can easily partition the list by separating the nodes into two lists based on their value relative to x.
• The challenge is to ensure that the relative order of nodes in each partition is maintained.
• By iterating through the original list and adding nodes to two new lists, we can preserve the order and later merge the lists together.
Steps:
• Initialize two dummy nodes: one for values less than x and one for values greater than or equal to x.
• Iterate through the linked list and append each node to the appropriate dummy node's next pointer.
• Once the iteration is complete, link the last node of the first list to the second list's head.
• Return the merged list starting from the node next to the first dummy node.
Empty Inputs:
• If the input linked list is empty (head is null), the output should also be null.
Large Inputs:
• Ensure the solution can handle up to 200 nodes efficiently.
Special Values:
• If all nodes have values less than x or greater than or equal to x, the list should still maintain its relative order.
Constraints:
• The solution must not modify the relative order of nodes within each partition.
Creates two dummy nodes `dummy1` and `dummy2` to act as the heads of two new lists: one for nodes less than `x` and one for nodes greater than or equal to `x`.
3 : Variable Initialization
ListNode *p1 = dummy1, *p2 = dummy2;
Initializes pointers `p1` and `p2` to point to the dummy nodes.
4 : Loop Iteration
while (head) {
Iterates through the original linked list.
5 : Conditional
if (head->val < x) {
Checks if the current node's value is less than `x`.
6 : Node Manipulation
p1->next = head;
Appends the current node to the first list.
7 : Pointer Update
p1 = p1->next;
Moves the `p1` pointer to the next node in the first list.
8 : Conditional
} else {
If the current node's value is greater than or equal to `x`.
9 : Node Manipulation
p2->next = head;
Appends the current node to the second list.
10 : Pointer Update
p2 = p2->next;
Moves the `p2` pointer to the next node in the second list.
11 : Pointer Update
head = head->next;
Moves to the next node in the original linked list.
12 : Node Manipulation
p2->next =nullptr;
Sets the `next` pointer of the last node in the second list to `null`.
13 : Node Manipulation
p1->next = dummy2->next;
Connects the two lists by setting the `next` pointer of the last node in the first list to the head of the second list.
14 : Return
return dummy1->next;
Returns the head of the partitioned list, which is the `next` node of `dummy1`.
Best Case: O(n), where n is the number of nodes in the list. We perform a single pass through the list.
Average Case: O(n)
Worst Case: O(n), since we traverse the list once and then merge the partitions.
Description: The time complexity is linear because we iterate through the list once to partition the nodes.
Best Case: O(n)
Worst Case: O(n), where n is the number of nodes in the list, as we create two new lists to hold the partitions.
Description: The space complexity is linear due to the need to store the two partitioned lists.
