86. Partition List

Intuition

The problem requires partitioning the linked list around a value x such that all nodes with values less than x come before nodes with values greater than or equal to x. Importantly, the relative order of the nodes in each partition must be preserved. This suggests the need for two separate lists: one for nodes less than x and another for nodes greater than or equal to x. By combining these two lists at the end, we can achieve the desired partitioned list.

Approach

1. Create Dummy Nodes: Initialize two dummy nodes: slist for the "small" partition (nodes less than x) and blist for the "big" partition (nodes greater than or equal to x). These dummy nodes help simplify the list operations.
2. Pointers for Traversal: Use two pointers, small and big, to build the new lists.
3. Traverse and Partition: - Traverse the original list node by node. - If the current node's value is less than x, add it to the small list. - If the current node's value is greater than or equal to x, add it to the big list.
4. Combine the Lists: - After traversing the entire list, connect the end of the small list to the beginning of the big list. - Set the end of the big list to None to terminate the combined list.
5. Return New Head: The head of the partitioned list is the next node of the dummy slist.

Complexity

Time Complexity:

O(n), where n is the number of nodes in the list. Each node is visited exactly once.

Space Complexity:

O(1). No additional space proportional to the input size is used, only a few extra pointers are maintained.

Code

C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* slist = new ListNode();
        ListNode* blist = new ListNode();
        ListNode* small = slist;
        ListNode* big = blist;

        while (head != nullptr) {
            if (head->val < x) {
                small->next = head;
                small = small->next;
            } else {
                big->next = head;
                big = big->next;
            }
            head = head->next;
        }
        small->next = blist->next;
        big->next = nullptr;

        return slist->next;    
    }
};

Python

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        slist = ListNode(0)
        blist = ListNode(0)
        small = slist
        big = blist

        while head is not None:
            if head.val < x:
                small.next = head
                small = small.next
            else:
                big.next = head
                big = big.next
            head = head.next
        
        small.next = blist.next
        big.next = None

        return slist.next

Java

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode slist = new ListNode(0);
        ListNode blist = new ListNode(0);
        ListNode small = slist;
        ListNode big = blist;

        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        small.next = blist.next;
        big.next = null;

        return slist.next;
    }
}

JavaScript

var partition = function(head, x) {
    let slist = new ListNode();
    let blist = new ListNode();
    let small = slist;
    let big = blist;

    while (head !== null) {
        if (head.val < x) {
            small.next = head;
            small = small.next;
        } else {
            big.next = head;
            big = big.next;
        }
        head = head.next;
    }
    small.next = blist.next;
    big.next = null;

    return slist.next;    
};