Partition List — Solution in Python, Java & C++
Partition List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.
Partition List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Adobe and Bloomberg interviews.
- Difficulty: Medium
- Topics: Two Pointers
- Asked at: Amazon, Microsoft, Adobe, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list and a value x, rearrange the list so that every node with a value less than x comes before every node with a value greater than or equal to x.
Keep the original relative order of the nodes inside each of the two groups, and return the head of the rearranged list.
Example 1
Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: Smaller than 3: 1, 2, 2 (in their order); the rest: 4, 3, 5.
Example 2
Input: head = [2,1], x = 2
Output: [1,2]
Example 3
Input: head = [], x = 0
Output: []
Constraints
The number of nodes in the list is in the range [0, 200]-100 <= Node.val <= 100-200 <= x <= 200
Hints for Partition List
Hint 1
The answer is a stable split: the small nodes in order, followed by the large nodes in order.
Hint 2
Build two separate lists while walking the original once — one for values
< x, one for the rest.Hint 3
Give each list a dummy head and a tail pointer; at the end link the small list's tail to the large list's head, and end the large list with null.
How to solve Partition List
Distribute the nodes into two chains as you meet them — values below x and the rest — then join the chains. Appending at a tail keeps each chain in its original order.
Approach
- Create dummy heads
smallandlargewith tailssandl. - Walk the list; append each node to
sif its value is< x, otherwise tol. - Set
l.next = null(the last large node may still point into the old list). - Set
s.next = large.nextand returnsmall.next.
Why it works
Each node is appended exactly once to the chain its value selects, and appending preserves the order of arrival, so each group keeps its relative order. Joining small before large puts every smaller value first.
Complexity
- Time —
O(n) - Space —
O(1) — the nodes are relinked, not copied
Pitfalls
- Forgetting
l.next = nullcan leave a cycle back into the small chain. - Values equal to
xbelong to the second group. - Swapping values in place (like an array partition) breaks the required stable order.
Reference solution
Python
from typing import Optional
def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
small = ListNode(0)
large = ListNode(0)
s, l = small, large
while head:
if head.val < x:
s.next = head
s = head
else:
l.next = head
l = head
head = head.next
l.next = None
s.next = large.next
return small.nextJava
public static ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0), large = new ListNode(0), s = small, l = large;
while (head != null) {
if (head.val < x) { s.next = head; s = head; }
else { l.next = head; l = head; }
head = head.next;
}
l.next = null;
s.next = large.next;
return small.next;
}C++
ListNode* partition(ListNode* head, int x) {
ListNode small(0), large(0);
ListNode *s = &small, *l = &large;
while (head) {
if (head->val < x) { s->next = head; s = head; }
else { l->next = head; l = head; }
head = head->next;
}
l->next = nullptr;
s->next = large.next;
return small.next;
}JavaScript
var partition = function(head, x) {
var small = new ListNode(0), large = new ListNode(0), s = small, l = large;
while (head !== null) {
if (head.val < x) { s.next = head; s = head; }
else { l.next = head; l = head; }
head = head.next;
}
l.next = null;
s.next = large.next;
return small.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 165 two pointers problems · the whole catalogue
Learn the technique: Two Pointers Technique