Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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/Output Specifications
- Input: Head of a linked list and integer x
- Output: Head of the partitioned linked list
- Constraints:
- The number of nodes in the list is in the range [0, 200]
- -100 <= Node.val <= 100
- -200 <= x <= 200
Examples
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]
Solutions
Approach 1: Two Dummy Lists
This approach creates two separate lists - one for nodes less than x and one for nodes greater than or equal to x, then concatenates them.
Algorithm:
- Create two dummy heads for smaller and greater/equal lists
- Traverse the original list
- For each node, add it to the appropriate list based on its value
- Connect the end of smaller list to the beginning of greater/equal list
- Set the end of greater/equal list to null
- Return the head of the smaller list (skip dummy)
Python:
def partition(head, x):
"""
Partition linked list around value x using two dummy lists
Time: O(n)
Space: O(1)
"""
# Create dummy heads for smaller and greater/equal lists
smaller_dummy = ListNode(0)
greater_dummy = ListNode(0)
smaller_tail = smaller_dummy
greater_tail = greater_dummy
current = head
while current:
if current.val < x:
smaller_tail.next = current
smaller_tail = smaller_tail.next
else:
greater_tail.next = current
greater_tail = greater_tail.next
current = current.next
# Connect smaller list to greater/equal list
smaller_tail.next = greater_dummy.next
greater_tail.next = None
return smaller_dummy.next
Java:
class Solution {
/**
* Partition linked list around value x using two dummy lists
* Time: O(n)
* Space: O(1)
*/
public ListNode partition(ListNode head, int x) {
// Create dummy heads for smaller and greater/equal lists
ListNode smallerDummy = new ListNode(0);
ListNode greaterDummy = new ListNode(0);
ListNode smallerTail = smallerDummy;
ListNode greaterTail = greaterDummy;
ListNode current = head;
while (current != null) {
if (current.val < x) {
smallerTail.next = current;
smallerTail = smallerTail.next;
} else {
greaterTail.next = current;
greaterTail = greaterTail.next;
}
current = current.next;
}
// Connect smaller list to greater/equal list
smallerTail.next = greaterDummy.next;
greaterTail.next = null;
return smallerDummy.next;
}
}
Go:
// partition - Partition linked list around value x using two dummy lists
// Time: O(n)
// Space: O(1)
func partition(head *ListNode, x int) *ListNode {
// Create dummy heads for smaller and greater/equal lists
smallerDummy := &ListNode{Val: 0}
greaterDummy := &ListNode{Val: 0}
smallerTail := smallerDummy
greaterTail := greaterDummy
current := head
for current != nil {
if current.Val < x {
smallerTail.Next = current
smallerTail = smallerTail.Next
} else {
greaterTail.Next = current
greaterTail = greaterTail.Next
}
current = current.Next
}
// Connect smaller list to greater/equal list
smallerTail.Next = greaterDummy.Next
greaterTail.Next = nil
return smallerDummy.Next
}
JavaScript:
/**
* Partition linked list around value x using two dummy lists
* Time: O(n)
* Space: O(1)
*/
function partition(head, x) {
// Create dummy heads for smaller and greater/equal lists
const smallerDummy = new ListNode(0);
const greaterDummy = new ListNode(0);
let smallerTail = smallerDummy;
let greaterTail = greaterDummy;
let current = head;
while (current !== null) {
if (current.val < x) {
smallerTail.next = current;
smallerTail = smallerTail.next;
} else {
greaterTail.next = current;
greaterTail = greaterTail.next;
}
current = current.next;
}
// Connect smaller list to greater/equal list
smallerTail.next = greaterDummy.next;
greaterTail.next = null;
return smallerDummy.next;
}
C#:
public class Solution {
/// <summary>
/// Partition linked list around value x using two dummy lists
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode Partition(ListNode head, int x) {
// Create dummy heads for smaller and greater/equal lists
ListNode smallerDummy = new ListNode(0);
ListNode greaterDummy = new ListNode(0);
ListNode smallerTail = smallerDummy;
ListNode greaterTail = greaterDummy;
ListNode current = head;
while (current != null) {
if (current.val < x) {
smallerTail.next = current;
smallerTail = smallerTail.next;
} else {
greaterTail.next = current;
greaterTail = greaterTail.next;
}
current = current.next;
}
// Connect smaller list to greater/equal list
smallerTail.next = greaterDummy.next;
greaterTail.next = null;
return smallerDummy.next;
}
}
Approach 2: In-Place Partitioning
This approach partitions the list in-place by moving nodes to the appropriate positions.
Algorithm:
- Find the first node with value >= x
- Traverse the rest of the list
- For each node with value < x, move it before the first >= x node
- Update pointers accordingly
Python:
def partitionInPlace(head, x):
"""
Partition linked list in-place around value x
Time: O(n)
Space: O(1)
"""
if not head or not head.next:
return head
# Find first node with value >= x
first_greater = head
while first_greater and first_greater.val < x:
first_greater = first_greater.next
if not first_greater:
return head # All nodes are smaller than x
# Move smaller nodes before first_greater
current = first_greater.next
while current:
if current.val < x:
# Move current before first_greater
temp = current.next
current.next = first_greater
first_greater = current
current = temp
else:
current = current.next
return head
Java:
class Solution {
/**
* Partition linked list in-place around value x
* Time: O(n)
* Space: O(1)
*/
public ListNode partitionInPlace(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
// Find first node with value >= x
ListNode firstGreater = head;
while (firstGreater != null && firstGreater.val < x) {
firstGreater = firstGreater.next;
}
if (firstGreater == null) {
return head; // All nodes are smaller than x
}
// Move smaller nodes before firstGreater
ListNode current = firstGreater.next;
while (current != null) {
if (current.val < x) {
// Move current before firstGreater
ListNode temp = current.next;
current.next = firstGreater;
firstGreater = current;
current = temp;
} else {
current = current.next;
}
}
return head;
}
}
Go:
// partitionInPlace - Partition linked list in-place around value x
// Time: O(n)
// Space: O(1)
func partitionInPlace(head *ListNode, x int) *ListNode {
if head == nil || head.Next == nil {
return head
}
// Find first node with value >= x
firstGreater := head
for firstGreater != nil && firstGreater.Val < x {
firstGreater = firstGreater.Next
}
if firstGreater == nil {
return head // All nodes are smaller than x
}
// Move smaller nodes before firstGreater
current := firstGreater.Next
for current != nil {
if current.Val < x {
// Move current before firstGreater
temp := current.Next
current.Next = firstGreater
firstGreater = current
current = temp
} else {
current = current.Next
}
}
return head
}
JavaScript:
/**
* Partition linked list in-place around value x
* Time: O(n)
* Space: O(1)
*/
function partitionInPlace(head, x) {
if (head === null || head.next === null) {
return head;
}
// Find first node with value >= x
let firstGreater = head;
while (firstGreater !== null && firstGreater.val < x) {
firstGreater = firstGreater.next;
}
if (firstGreater === null) {
return head; // All nodes are smaller than x
}
// Move smaller nodes before firstGreater
let current = firstGreater.next;
while (current !== null) {
if (current.val < x) {
// Move current before firstGreater
const temp = current.next;
current.next = firstGreater;
firstGreater = current;
current = temp;
} else {
current = current.next;
}
}
return head;
}
C#:
public class Solution {
/// <summary>
/// Partition linked list in-place around value x
/// Time: O(n)
/// Space: O(1)
/// </summary>
public ListNode PartitionInPlace(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
// Find first node with value >= x
ListNode firstGreater = head;
while (firstGreater != null && firstGreater.val < x) {
firstGreater = firstGreater.next;
}
if (firstGreater == null) {
return head; // All nodes are smaller than x
}
// Move smaller nodes before firstGreater
ListNode current = firstGreater.next;
while (current != null) {
if (current.val < x) {
// Move current before firstGreater
ListNode temp = current.next;
current.next = firstGreater;
firstGreater = current;
current = temp;
} else {
current = current.next;
}
}
return head;
}
}
Key Insights
- Two-list approach: Create separate lists for smaller and greater/equal values
- Dummy nodes: Simplify edge cases and pointer management
- Relative order preservation: Maintain the original order within each partition
- Single pass: Process each node exactly once
- Space efficiency: Use O(1) extra space by reusing existing nodes
Edge Cases
- Empty list
- Single node list
- All nodes are smaller than x
- All nodes are greater than or equal to x
- x is the minimum value
- x is the maximum value
Test Cases
# Test case 1: Normal case
head1 = ListNode(1)
head1.next = ListNode(4)
head1.next.next = ListNode(3)
head1.next.next.next = ListNode(2)
head1.next.next.next.next = ListNode(5)
head1.next.next.next.next.next = ListNode(2)
# partition(head1, 3) -> [1,2,2,4,3,5]
# Test case 2: All nodes smaller
head2 = ListNode(1)
head2.next = ListNode(2)
head2.next.next = ListNode(3)
# partition(head2, 5) -> [1,2,3]
# Test case 3: All nodes greater or equal
head3 = ListNode(4)
head3.next = ListNode(5)
head3.next.next = ListNode(6)
# partition(head3, 3) -> [4,5,6]
# Test case 4: Single node
head4 = ListNode(1)
# partition(head4, 2) -> [1]
Follow-up Questions
- How would you handle duplicate values?
- Can you solve this with O(1) space and O(1) time?
- How would you partition into three groups (less, equal, greater)?
- What if you need to maintain the original list?
Common Mistakes
- Not properly connecting the two lists
- Forgetting to set the end of the greater list to null
- Not handling edge cases like empty lists
- Incorrect pointer management during traversal
- Not preserving the relative order of nodes
- Memory leaks when not properly managing pointers