🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires partitioning the linked list around a value x
such that all nodes with values less than x
come before nodes with values greater than or equal to x
. Importantly, the relative order of the nodes in each partition must be preserved. This suggests the need for two separate lists: one for nodes less than x
and another for nodes greater than or equal to x
. By combining these two lists at the end, we can achieve the desired partitioned list.
Approach
- Create Dummy Nodes: Initialize two dummy nodes:
slist
for the "small" partition (nodes less thanx
) andblist
for the "big" partition (nodes greater than or equal tox
). These dummy nodes help simplify the list operations. - Pointers for Traversal: Use two pointers,
small
andbig
, to build the new lists. - Traverse and Partition:
- Traverse the original list node by node.
- If the current node's value is less than
x
, add it to thesmall
list. - If the current node's value is greater than or equal tox
, add it to thebig
list. - Combine the Lists:
- After traversing the entire list, connect the end of the
small
list to the beginning of thebig
list. - Set the end of thebig
list toNone
to terminate the combined list. - Return New Head: The head of the partitioned list is the next node of the dummy
slist
.
Complexity
Time Complexity:
O(n), where
n is the number of nodes in the list. Each node is visited exactly once.
Space Complexity:
O(1)
. No additional space proportional to the input size is used, only a few extra pointers are maintained.
Code
C++
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* slist = new ListNode();
ListNode* blist = new ListNode();
ListNode* small = slist;
ListNode* big = blist;
while (head != nullptr) {
if (head->val < x) {
small->next = head;
small = small->next;
} else {
big->next = head;
big = big->next;
}
head = head->next;
}
small->next = blist->next;
big->next = nullptr;
return slist->next;
}
};
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
slist = ListNode(0)
blist = ListNode(0)
small = slist
big = blist
while head is not None:
if head.val < x:
small.next = head
small = small.next
else:
big.next = head
big = big.next
head = head.next
small.next = blist.next
big.next = None
return slist.next
Java
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode slist = new ListNode(0);
ListNode blist = new ListNode(0);
ListNode small = slist;
ListNode big = blist;
while (head != null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
big.next = head;
big = big.next;
}
head = head.next;
}
small.next = blist.next;
big.next = null;
return slist.next;
}
}
JavaScript
var partition = function(head, x) {
let slist = new ListNode();
let blist = new ListNode();
let small = slist;
let big = blist;
while (head !== null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
big.next = head;
big = big.next;
}
head = head.next;
}
small.next = blist.next;
big.next = null;
return slist.next;
};