86. Partition List
mediumReorder a linked list so all nodes less than x come before all nodes greater than or equal to x — preserving the original relative order. The two-dummy-heads trick that makes the logic embarrassingly simple compared to a single in-place rewire.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
The number of nodes in the list is in the range [0, 200].-100 <= Node.val <= 100-200 <= x <= 200
Examples
Example 1
head = [1,4,3,2,5,2], x = 3[1,2,2,4,3,5]Example 2
head = [2,1], x = 2[1,2]Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Build two separate lists as you walk: one for nodes < x, one for nodes >= x.
Hint 2
Use two dummy heads to avoid special-casing the first append into each list.
Hint 3
After the single pass, stitch lessTail.next = greaterDummy.next and terminate greaterTail.next = null.
Solution approach
Reveal approach
Two-dummy-head partition. Allocate two dummy heads, lessDummy and greaterDummy, with tail pointers lessTail = lessDummy and greaterTail = greaterDummy. Walk the original list once. For each node, if node.val < x append it to the 'less' chain (lessTail.next = node; lessTail = node); otherwise append it to the 'greater' chain. After the pass, stitch the two chains: lessTail.next = greaterDummy.next, and crucially set greaterTail.next = null to terminate the list (otherwise you can leak into the original tail's old next). Return lessDummy.next. Because you append in encounter order, the relative order inside each partition is preserved. O(n) time, O(1) extra space (the dummy nodes are constant).
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- linked-list
- dummy-head
- two-pointers
- pointer-rewiring
Related problems
- 328. Odd Even Linked List
- 75. Sort Colors
- 143. Reorder List
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Microsoft
- Bloomberg
Practice these live with InterviewChamp.AI
Drill Partition List and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →