Dare2Solve
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.
Create Dummy Nodes: Initialize two dummy nodes: slist
for the "small" partition (nodes less than x
) and blist
for the "big" partition (nodes greater than or equal to x
). These dummy nodes help simplify the list operations.
Pointers for Traversal: Use two pointers, small
and big
, to build the new lists.
Traverse and Partition:
x
, add it to the small
list.x
, add it to the big
list.Combine the Lists:
small
list to the beginning of the big
list.big
list to None
to terminate the combined list.Return New Head: The head of the partitioned list is the next node of the dummy slist
.
O(n), where
n` is the number of nodes in the list. Each node is visited exactly once.
O(1)
. No additional space proportional to the input size is used, only a few extra pointers are maintained.
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;
}
};
# 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
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;
}
}
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;
};