Partition List - Leetcode Solution

Problem:

Given 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

Solution:

Approach: Two-Pointer Approach

First, we need to create two linked lists, one for all the nodes less than the given value x and the second for all the nodes greater than or equal to the given value.

We will iterate over the given linked list and compare each node’s value with the given value and add the node to either of the two lists.

Once done, we will merge these two lists and return the head of the newly reconstructed linked list.

Let’s see how we can implement this algorithm.

Step 1: Create two linked lists, one for all the nodes less than the given value and the second for all the nodes greater than or equal to the given value. We will initialize these two lists with the node values as 0.

ListNode less = new ListNode(0); ListNode greaterOrEqual = new ListNode(0);

ListNode lesserNode = less; ListNode greaterOrEqualNode = greaterOrEqual;

Step 2: Iterate over the given linked list and compare each node’s value with the given value and add the node to either of the two lists.

while (head != null) { if (head.val < x) { lesserNode.next = head; lesserNode = lesserNode.next; } else { greaterOrEqualNode.next = head; greaterOrEqualNode = greaterOrEqualNode.next; } head = head.next; }

Step 3: Once done, we will merge these two lists and return the head of the newly reconstructed linked list.

greaterOrEqualNode.next = null; lesserNode.next = greaterOrEqual.next; return less.next;

Complete Code:

public ListNode partition(ListNode head, int x) {

ListNode less = new ListNode(0);
ListNode greaterOrEqual = new ListNode(0);

ListNode lesserNode = less;
ListNode greaterOrEqualNode = greaterOrEqual;

while (head != null) {
    if (head.val < x) {
        lesserNode.next = head;
        lesserNode = lesserNode.next;
    } else {
        greaterOrEqualNode.next = head;
        greaterOrEqualNode = greaterOrEqualNode.next;
    }
    head = head.next;
}

greaterOrEqualNode.next = null;
lesserNode.next = greaterOrEqual.next;
return less.next;

}

Time Complexity: O(n)

Space Complexity: O(1)

1