Leetcode Partition List problem solution

In this Leetcode Partition List problem solution we have 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.

Topics we are covering

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

coding problems solutions