Partition List LeetCode Solution

Last updated on January 19th, 2025 at 06:07 pm

Here, we see a Partition List LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Linked List, Two-Pointers

Level of Question

Medium

Partition List LeetCode Solution

Partition List LeetCode Solution

1. 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]

2. Coding Pattern Used in Solution

The coding pattern used in this code is “Linked List Partitioning”. The goal of this pattern is to rearrange the nodes of a linked list into two partitions based on a condition (in this case, whether the node’s value is less than x or not) while maintaining the relative order of nodes in each partition.

3. Code Implementation in Different Languages

3.1 Partition List 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;     
    }
};

3.2 Partition List 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.3 Partition List 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    
};

3.4 Partition List 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

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(1)
JavaO(n)O(1)
JavaScriptO(n)O(1)
PythonO(n)O(1)
  • The code is efficient because it processes the linked list in a single pass O(n) and uses constant space O(1).
  • The relative order of nodes in each partition is preserved because nodes are appended to the end of their respective partitions as they are encountered.
  • The implementation is consistent across all languages, with minor syntactic differences.
Scroll to Top