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