Partition List [Linked List]

86.Partition List

Linked List

Two Pointers

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. Maintain the relative order of the nodes in each of the two partitions.

Example:

Input:

head = [1,4,3,2,5,2]
x = 3

→

Output:

[1,2,2,4,3,5]

All elements < 3 come before elements ≥ 3. Relative order is preserved.

Algorithm:

1. Create two dummy nodes for two sublists:
   • list1: nodes less than x
   • list2: nodes greater than or equal to x
2. Traverse original list:
   • Add current node to appropriate sublist
   • Move respective pointer forward
3. Connect the sublists:
   • Set list2's end to null
   • Connect list1's end to list2's start

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode partition(ListNode head, int x) {
    // Create two dummy nodes for two sublists
    ListNode dummy1 = new ListNode(0), dummy2 = new ListNode(0);
    ListNode curr = head, list1 = dummy1, list2 = dummy2;

    // Build two sublists
    while (curr != null) {
        if (curr.val < x) {
            list1.next = curr;        // Add to less than x list
            list1 = list1.next;
        } else {
            list2.next = curr;        // Add to greater than or equal list
            list2 = list2.next;
        }
        curr = curr.next;
    }

    // Connect the two sublists
    list2.next = null;            // End of second list
    list1.next = dummy2.next;        // Connect first list to second
    return dummy1.next;
}

Python Solution:

def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
    # Create dummy nodes
    dummy1 = list1 = ListNode(0)
    dummy2 = list2 = ListNode(0)
    curr = head
    
    # Build two sublists
    while curr:
        if curr.val < x:
            list1.next = curr
            list1 = list1.next
        else:
            list2.next = curr
            list2 = list2.next
        curr = curr.next
    
    # Connect lists
    list2.next = None
    list1.next = dummy2.next
    
    return dummy1.next

C++ Solution:

ListNode* partition(ListNode* head, int x) {
    ListNode* dummy1 = new ListNode(0);
    ListNode* dummy2 = new ListNode(0);
    ListNode *list1 = dummy1, *list2 = dummy2;
    ListNode* curr = head;
    
    // Build sublists
    while (curr) {
        if (curr->val < x) {
            list1->next = curr;
            list1 = list1->next;
        } else {
            list2->next = curr;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    
    // Connect lists
    list2->next = nullptr;
    list1->next = dummy2->next;
    
    ListNode* result = dummy1->next;
    delete dummy1;
    delete dummy2;
    return result;
}