Coding Interview PatternsPartition List
MediumIn-Place Manipulation of a Linked List
Partition List
Explanation & Solution
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.
Input:head = [1,4,3,2,5,2], x = 3
0
1
1
4
2
3
3
2
4
5
5
2
Output:[1,2,2,4,3,5]
0
1
1
2
2
2
3
4
4
3
5
5
Explanation: Nodes less than 3: [1,2,2]. Nodes ≥ 3: [4,3,5]. Concatenated: [1,2,2,4,3,5].
Constraints
- The number of nodes in the list is in the range
[0, 200] -100 <= Node.val <= 100-200 <= x <= 200
Approach
In-Place Manipulation of a Linked List pattern
1. Create Two Dummy Heads
beforeHead— dummy head for nodes with values less thanx.afterHead— dummy head for nodes with values greater than or equal tox.- Use
beforeandafteras tails of each partition.
2. Traverse and Partition
- Walk through each node in the original list.
- If
curr.val < x, append it to thebeforelist. - Otherwise, append it to the
afterlist. - Advance to the next node.
3. Connect the Two Partitions
- Set
after.next = nullto terminate the "after" list. - Link the end of the "before" list to the start of the "after" list:
before.next = afterHead.next.
4. Return the Result
- The merged list starts at
beforeHead.next. - Collect values and return as an array.
🧠 Key Insight
- By maintaining two separate lists and merging them at the end, we preserve the original relative order within each partition.
Time
O(n)single pass through the list.Space
O(1)only pointer variables (no new nodes created, we reuse existing nodes).Visualization
Input:
Linked List Traversal
—
Press play to start traversal
Slow (S)Fast (F)Both
8 steps