Partition List

MEDIUM

Description

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]

Constraints:

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Approaches

Checkout 2 different approaches to solve Partition List. Click on different approaches to view the approach and algorithm in detail.

Using Auxiliary Lists

This approach involves converting the linked list into a more flexible data structure, like an array or list, to make partitioning easier. We iterate through the original list, segregating nodes into two separate lists based on the pivot value x. One list holds nodes with values less than x, and the other holds nodes with values greater than or equal to x. After populating these lists, we link them together to form the final partitioned linked list.

Algorithm

1. Create two auxiliary ArrayLists: one to store nodes with values less than x (lesserNodes) and another for nodes with values greater than or equal to x (greaterOrEqualNodes).
1. Traverse the input linked list from the head.
1. For each node encountered, check its value. If node.val < x, add the node to lesserNodes. Otherwise, add it to greaterOrEqualNodes.
1. After the entire list has been traversed, the two ArrayLists will contain all the nodes, partitioned and with their relative order preserved within each partition.
1. Create a new dummy ListNode to serve as the starting point for the result list.
1. Iterate through lesserNodes and append each node to the new list.
1. Then, iterate through greaterOrEqualNodes and append each node to the end of the new list.
1. Finally, set the next pointer of the last node in the newly formed list to null to prevent cycles.
1. Return the next of the dummy node, which is the head of the final partitioned list.

The core idea is to offload the linked list nodes into two separate lists. This simplifies the partitioning logic as we don't have to manage next pointers during the segregation phase.

First, we iterate through the linked list once. During this traversal, we check each node's value against x. If the value is smaller, we add the node to a lesserNodes list. If it's greater or equal, we add it to a greaterOrEqualNodes list. Because we add nodes to the end of these lists in the order we encounter them, the original relative ordering within each partition is naturally preserved.

Once the segregation is complete, we construct the new linked list. We create a dummy head to simplify the building process. We first link all nodes from the lesserNodes list, and then we link all nodes from the greaterOrEqualNodes list. It's crucial to set the next pointer of the very last node to null to correctly terminate the list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        // Store nodes in two separate lists
        java.util.List<ListNode> lesserNodes = new java.util.ArrayList<>();
        java.util.List<ListNode> greaterOrEqualNodes = new java.util.ArrayList<>();

        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                lesserNodes.add(current);
            } else {
                greaterOrEqualNodes.add(current);
            }
            current = current.next;
        }

        // Reconstruct the linked list
        ListNode dummy = new ListNode(0);
        ListNode newTail = dummy;

        for (ListNode node : lesserNodes) {
            newTail.next = node;
            newTail = newTail.next;
        }

        for (ListNode node : greaterOrEqualNodes) {
            newTail.next = node;
            newTail = newTail.next;
        }

        // Terminate the list
        newTail.next = null;

        return dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(N)Space Complexity: O(N)

Pros and Cons

Pros:

Conceptually straightforward and easy to implement.
Separates the concern of partitioning from the complexities of linked list pointer manipulation.

Cons:

Requires O(N) extra space for the auxiliary lists, which is inefficient for large inputs.
This approach is not in-place; it reconstructs the list structure rather than just rearranging pointers.

Code Solutions

Checking out 5 solutions in different languages for Partition List. Click on different languages to view the code.

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode Partition ( ListNode head , int x ) { ListNode l = new ListNode (); ListNode r = new ListNode (); ListNode tl = l , tr = r ; for (; head != null ; head = head . next ) { if ( head . val < x ) { tl . next = head ; tl = tl . next ; } else { tr . next = head ; tr = tr . next ; } } tr . next = null ; tl . next = r . next ; return l . next ; } }

Video Solution

Watch the video walkthrough for Partition List

Patterns:

Two Pointers

Data Structures:

Linked List

Companies:

Adobe |Amazon |Apple |Bloomberg |