Partition List LeetCode Solution

Last updated on October 9th, 2024 at 10:15 pm

Here, We see Partition List LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Linked List, Two-Pointers

Level of Question

Medium

Partition List LeetCode Solution

Partition List LeetCode Solution

Problem Statement

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.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

1. Partition List Leetcode Solution C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
	ListNode* left = new ListNode(), *right = new ListNode();
	ListNode *newHead = left, *mid = right;

	while(head) {
		if(head->val < x) {
			left->next = head;
			left = left->next;
		} 
		else {
			right->next = head;
			right = right->next;
		}
		head = head->next;
	}
	left->next = mid->next;
	right->next = NULL;
	return newHead->next;     
    }
};

2. Partition List Leetcode Solution Java

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        
        ListNode leftTail = left;
        ListNode rightTail = right;
        
        while(head != null){
            if(head.val < x){
                leftTail.next = head;
                leftTail = leftTail.next;
            }
            else{
                rightTail.next = head;
                rightTail = rightTail.next;
            }
            head = head.next;
        }
        
        leftTail.next = right.next;
        rightTail.next = null;
        
        return left.next;        
    }
}

3. Partition List Leetcode Solution JavaScript

var partition = function(head, x) {
    let fdum = new ListNode(0), bdum = new ListNode(0),
        front = fdum, back = bdum, curr = head
    while (curr) {
        if (curr.val < x)front.next = curr, front = curr
        else back.next = curr, back = curr
        curr = curr.next
    }
    front.next = bdum.next, back.next = null
    return fdum.next    
};

4. Partition List Leetcode Solution Python

class Solution(object):
    def partition(self, head, x):
        h1, h2 = None, None
        n      = head
        while n:
            if n.val<x:
                if h1:
                    n1.next = n
                else:
                    h1      = n
                n1 = n
            else:
                if h2:
                    n2.next = n
                else:
                    h2      = n
                n2 = n
            n = n.next
        if h1:
            n1.next = h2
        if h2:
            n2.next = None
        return h1 or h2
Scroll to Top