Partition List Problem Solution

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]

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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment