Partition List 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.
Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]
Table of Contents
Partition List Problem Solution
Problem Solution In Python
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
dummy1 = ListNode(0)
head1 = dummy1
dummy2 = ListNode(0)
head2 = dummy2
while head:
if head.val < x:
head1.next = head
head1 = head1.next
else:
head2.next = head
head2 = head2.next
head = head.next
head2.next = None
head1.next = dummy2.next
return dummy1.next
Problem Solution In Java
public ListNode partition(ListNode head, int x) {
if(head==null||head.next==null) return head;
ListNode first=null;
ListNode firstHead=null;
ListNode secondHead=null;
ListNode second=null;
ListNode cur=head;
while(cur!=null){
if(cur.val<x){
if(first==null) {first=cur; firstHead=first;}
else {first.next=cur; first=first.next;}
}
else{
if(second==null) {second=cur; secondHead=second;}
else {second.next=cur; second=second.next;}
}
cur=cur.next;
}
if(first==null) {
second.next=null;
return secondHead;
}
else if(second==null){
return firstHead;
}else{
second.next=null;
first.next=secondHead;
}
return firstHead;
}
Problem Solution In C++
ListNode* partition(ListNode* head, int target) {
ListNode* fake_head = new ListNode(target - 1);
fake_head->next = head;
ListNode* previous = fake_head;
ListNode* partition = fake_head;
ListNode* current = head;
while (current) {
if (current->val < target) {
if (previous->val < target) {
previous = current;
} else {
previous->next = current->next;
current->next = partition->next;
partition->next = current;
}
partition = current;
} else {
previous = current;
}
current = previous->next;
}
head = fake_head->next;
fake_head->next = NULL;
delete fake_head;
return head;
}
Problem Solution In C
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode *p, *q, node, node2;
node.next = head;
q = &node;
p = &node2;
while(q->next){
if(q->next->val >= x){
p->next = q->next;
p = p->next;
q->next = p->next;
}
else q = q->next;
}
p->next = NULL;
q->next = node2.next;
return node.next;
}