Partition List solution and explanation
Google
9 more videos on this problem
Partition List - Linked List - Leetcode 86NeetCode · 7:40 · 46K views
LeetCode Partition List Explained - JavaNick White · 4:16 · 20K views
Partition List | Live Coding with Explanation | Leetcode - 86Algorithms Made Easy · 6:03 · 15K views
#Leetcode 86. #Partition ListCode with Alisha · 11:44 · 14K views
[Java] Leetcode 86. Partition List [LinkedList #8]Eric Programming · 5:46 · 2K views
Mastering LeetCode 86. Partition List with Two Pointers | Live Coding with vanAmsenvanAmsen · 9:40 · 2K views
LeetCode Problem 86 - Partition List - Python Linked List Solution to Beat 98%KNuggies · 5:46 · 536 views
Leetcode 86: Partition ListAlgorithms Casts · 9:37 · 530 views
Partition List | Leetcode 86 | Live Coding sessionCoding Decoded · 11:43 · 471 views
Partition List | Partition Linked List | LeetCode 86Java2Novice · 6:14 · 397 views
The 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.
Example 1:
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2 Output: [1,2]
Constraints:
- The number of nodes in the list is in the range
[0, 200]. -100 <= Node.val <= 100-200 <= x <= 200
Approach overview
Problem Overview: Given the head of a linked list and an integer x, rearrange the nodes so that all nodes with values less than x appear before nodes greater than or equal to x. The relative order of nodes in each partition must remain the same.
Approach 1: Two-Pointer Partition Lists (O(n) time, O(1) extra space)
This approach builds two temporary chains while traversing the list once. One list stores nodes with values < x, and the other stores nodes with values >= x. Use two pointers (usually dummy heads) to append nodes as you iterate through the original list. After processing all nodes, connect the end of the smaller list to the head of the larger list. The key insight is that you never create new nodes—you only rewire next pointers—so the relative order inside each partition stays intact. This technique is a classic application of linked list manipulation combined with the two pointers pattern.
Approach 2: In-Place Rearrangement (O(n) time, O(1) space)
Instead of maintaining two separate lists, this method reorganizes nodes directly inside the existing structure. Track the tail of the "less than x" region while scanning the list. When a node with value < x appears after larger elements, detach it and move it right after the partition boundary. Pointer updates must be handled carefully to avoid breaking the list. The advantage is strict constant extra space with no additional dummy lists. This version emphasizes pointer operations and deeper understanding of linked list structure.
Recommended for interviews: The two-pointer partition list method is what most interviewers expect. It is simple, safe, and easy to reason about while maintaining stable ordering. The in-place rearrangement approach demonstrates stronger pointer manipulation skills and can impress interviewers if implemented cleanly. Showing the straightforward partition first proves correctness; discussing the in-place optimization shows deeper mastery of two pointer and linked list techniques.
Approach 1: Two-Pointer Approach
This approach involves using two separate linked lists to store nodes that are less than x and nodes that are greater than or equal to x. You traverse the original list and attach each node to the appropriate list. Finally, you connect the two lists together to form the partitioned list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
less_head = ListNode()
greater_head = ListNode()
less, greater = less_head, greater_head
while head:
if head.val < x:
less.next = head
less = less.next
else:
greater.next = head
greater = greater.next
head = head.next
greater.next = None
less.next = greater_head.next
return less_head.nextclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode lessHead = new ListNode(0);
ListNode greaterHead = new ListNode(0);
ListNode less = lessHead, greater = greaterHead;
while (head != null) {
if (head.val < x) {
less.next = head;
less = less.next;
} else {
greater.next = head;
greater = greater.next;
}
head = head.next;
}
greater.next = null;
less.next = greaterHead.next;
return lessHead.next;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode lessHead(0), greaterHead(0);
ListNode* less = &lessHead;
ListNode* greater = &greaterHead;
while (head) {
if (head->val < x) {
less->next = head;
less = less->next;
} else {
greater->next = head;
greater = greater->next;
}
head = head->next;
}
greater->next = nullptr;
less->next = greaterHead.next;
return lessHead.next;
}
};function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function partition(head, x) {
let lessHead = new ListNode(0);
let greaterHead = new ListNode(0);
let less = lessHead, greater = greaterHead;
while (head !== null) {
if (head.val < x) {
less.next = head;
less = less.next;
} else {
greater.next = head;
greater = greater.next;
}
head = head.next;
}
greater.next = null;
less.next = greaterHead.next;
return lessHead.next;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode lessHead = {0, NULL}, greaterHead = {0, NULL};
struct ListNode *less = &lessHead, *greater = &greaterHead;
while (head) {
if (head->val < x) {
less->next = head;
less = less->next;
} else {
greater->next = head;
greater = greater->next;
}
head = head->next;
}
greater->next = NULL;
less->next = greaterHead.next;
return lessHead.next;
}
// Helper functions and testing code are omitted for brevity.public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode Partition(ListNode head, int x) {
ListNode lessHead = new ListNode(0);
ListNode greaterHead = new ListNode(0);
ListNode less = lessHead, greater = greaterHead;
while (head != null) {
if (head.val < x) {
less.next = head;
less = less.next;
} else {
greater.next = head;
greater = greater.next;
}
head = head.next;
}
greater.next = null;
less.next = greaterHead.next;
return lessHead.next;
}
}This Python solution uses two pointers: one for nodes less than x and another for nodes greater or equal to x. By connecting the two groups at the end, the list is partitioned as required.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: In-Place Rearrangement Approach
This in-place rearrangement technique modifies the original list without the need of additional dummy nodes. This is accomplished by managing pointers to redefine segment connections efficiently.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
before_start = before_end = after_start = after_end = None
while head:
next_node = head.next
head.next = None
if head.val < x:
if before_start is None:
before_start = head
before_end = before_start
else:
before_end.next = head
before_end = before_end.next
else:
if after_start is None:
after_start = head
after_end = after_start
else:
after_end.next = head
after_end = after_end.next
head = next_node
if before_start is None:
return after_start
before_end.next = after_start
return before_startclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode beforeStart = null, beforeEnd = null, afterStart = null, afterEnd = null;
while (head != null) {
ListNode next = head.next;
head.next = null;
if (head.val < x) {
if (beforeStart == null) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd.next = head;
beforeEnd = head;
}
} else {
if (afterStart == null) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd.next = head;
afterEnd = head;
}
}
head = next;
}
if (beforeStart == null) {
return afterStart;
}
beforeEnd.next = afterStart;
return beforeStart;
}
}#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* beforeStart = nullptr;
ListNode* beforeEnd = nullptr;
ListNode* afterStart = nullptr;
ListNode* afterEnd = nullptr;
while (head != nullptr) {
ListNode* next = head->next;
head->next = nullptr;
if (head->val < x) {
if (beforeStart == nullptr) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd->next = head;
beforeEnd = beforeEnd->next;
}
} else {
if (afterStart == nullptr) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd->next = head;
afterEnd = afterEnd->next;
}
}
head = next;
}
if (beforeStart == nullptr) {
return afterStart;
}
beforeEnd->next = afterStart;
return beforeStart;
}
};function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function partition(head, x) {
let beforeStart = null, beforeEnd = null;
let afterStart = null, afterEnd = null;
while (head !== null) {
const next = head.next;
head.next = null;
if (head.val < x) {
if (beforeStart === null) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd.next = head;
beforeEnd = head;
}
} else {
if (afterStart === null) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd.next = head;
afterEnd = head;
}
}
head = next;
}
if (beforeStart === null) {
return afterStart;
}
beforeEnd.next = afterStart;
return beforeStart;
}#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode *beforeStart = NULL, *beforeEnd = NULL, *afterStart = NULL, *afterEnd = NULL;
while (head != NULL) {
struct ListNode *next = head->next;
head->next = NULL;
if (head->val < x) {
if (beforeStart == NULL) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd->next = head;
beforeEnd = head;
}
} else {
if (afterStart == NULL) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd->next = head;
afterEnd = head;
}
}
head = next;
}
if (beforeStart == NULL) {
return afterStart;
}
beforeEnd->next = afterStart;
return beforeStart;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode Partition(ListNode head, int x) {
ListNode beforeStart = null, beforeEnd = null, afterStart = null, afterEnd = null;
while (head != null) {
ListNode next = head.next;
head.next = null;
if (head.val < x) {
if (beforeStart == null) {
beforeStart = head;
beforeEnd = beforeStart;
} else {
beforeEnd.next = head;
beforeEnd = head;
}
} else {
if (afterStart == null) {
afterStart = head;
afterEnd = afterStart;
} else {
afterEnd.next = head;
afterEnd = head;
}
}
head = next;
}
if (beforeStart == null) {
return afterStart;
}
beforeEnd.next = afterStart;
return beforeStart;
}
}This Python solution rearranges nodes as the list is traversed. By maintaining two sets of pointers, we recombine the nodes efficiently to ensure a valid partitioned list.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Simulation
We create two linked lists l and r, one to store nodes less than x and the other to store nodes greater than or equal to x. Then we concatenate them.
The time complexity is O(n), where n is the length of the original linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function partition(head: ListNode | null, x: number): ListNode | null {
const [l, r] = [new ListNode(), new ListNode()];
let [tl, tr] = [l, r];
for (; head; head = head.next) {
if (head.val < x) {
tl.next = head;
tl = tl.next;
} else {
tr.next = head;
tr = tr.next;
}
}
tr.next = null;
tl.next = r.next;
return l.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
l, r := &ListNode{}, &ListNode{}
tl, tr := l, r
for ; head != nil; head = head.Next {
if head.Val < x {
tl.Next = head
tl = tl.Next
} else {
tr.Next = head
tr = tr.Next
}
}
tr.Next = nil
tl.Next = r.Next
return l.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn partition(head: Option<Box<ListNode>>, x: i32) -> Option<Box<ListNode>> {
let mut l = ListNode::new(0);
let mut r = ListNode::new(0);
let mut tl = &mut l;
let mut tr = &mut r;
let mut current = head;
while let Some(mut node) = current {
current = node.next.take();
if node.val < x {
tl.next = Some(node);
tl = tl.next.as_mut().unwrap();
} else {
tr.next = Some(node);
tr = tr.next.as_mut().unwrap();
}
}
tr.next = None;
tl.next = r.next;
l.next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n) |
| In-Place Rearrangement Approach | Time Complexity: O(n) |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Partition Lists | O(n) | O(1) | Best general solution. Clean logic using two dummy heads and stable ordering. |
| In-Place Rearrangement | O(n) | O(1) | When minimizing auxiliary structures and demonstrating advanced pointer manipulation. |
Frequently asked questions
Is Partition List easy or hard?
Partition List is considered a medium difficulty problem. The traversal itself is straightforward, but maintaining stable order while correctly updating pointers can be tricky for beginners working with linked lists.
How to solve Partition List in O(n)?
Iterate through the linked list once while maintaining two pointers representing the tails of two partitions: values less than x and values greater than or equal to x. Append each node to the appropriate list as you scan. After traversal, connect the smaller partition's tail to the head of the larger partition. This single pass guarantees O(n) time complexity.
What is the best approach for Partition List?
The two-pointer partition approach is the most common solution. Traverse the linked list once while building two chains: nodes less than x and nodes greater than or equal to x. Connect the two lists at the end. This runs in O(n) time and O(1) extra space while preserving the relative order of nodes.
What data structure is used in Partition List?
The problem operates entirely on a singly linked list. The solution relies on pointer manipulation, often with dummy head nodes and two pointer references to maintain partitions during traversal.
What is the time complexity of Partition List?
Partition List runs in O(n) time because each node in the linked list is visited exactly once. Pointer updates and comparisons are constant-time operations. Space complexity is O(1) since the algorithm only uses a few pointer references and does not allocate additional data structures proportional to input size.
Partition List Python or Java solution approach?
Python and Java solutions typically implement the two-pointer partition strategy. Create two dummy nodes for the 'less than x' and 'greater or equal to x' lists, iterate through the original list, attach nodes to the correct partition, and finally link the lists together.
Is Partition List asked at Google, Amazon, or Meta?
Partition List is a common linked list partitioning problem frequently seen in interviews at companies like Amazon, Google, and Meta. Variants of the problem appear in technical screens because they test pointer manipulation, stable ordering, and understanding of linked list traversal.