86. Partition List - Explanation

Problem Link

1. Brute Force

Intuition

We need to partition the linked list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each group.

The brute force approach extracts all values into two separate lists based on the partition condition, then writes them back to the original nodes. This simplifies the logic but requires extra space proportional to the list size.

Algorithm

1. Create two arrays: one for values less than x, another for values greater than or equal to x.
2. Traverse the linked list once, appending each value to the appropriate array.
3. Traverse the linked list again, overwriting node values in order: first all values from the "less" array, then all values from the "greater" array.
4. Return the head of the modified list.

# 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]:
        if not head:
            return None

        less, greater = [], []
        cur = head
        while cur:
            if cur.val < x:
                less.append(cur.val)
            else:
                greater.append(cur.val)
            cur = cur.next

        cur = head
        for val in less:
            cur.val = val
            cur = cur.next

        for val in greater:
            cur.val = val
            cur = cur.next

        return head

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

2. Two Pointers

Intuition

Instead of storing values in arrays, we can build two separate linked lists as we traverse: one for nodes less than x, one for nodes greater than or equal to x. Using dummy head nodes simplifies edge case handling.

At the end, we connect the tail of the "less" list to the head of the "greater" list, and terminate the "greater" list to avoid cycles. This achieves O(1) extra space by reusing the original nodes.

Algorithm

1. Create two dummy nodes as heads for the "left" (less than x) and "right" (greater or equal) lists.
2. Maintain tail pointers for both lists.
3. Traverse the original list:
   • If the current node's value is less than x, append it to the left list.
   • Otherwise, append it to the right list.
4. Connect the left list's tail to the right list's first real node (skip dummy).
5. Set the right list's tail's next to null to terminate the list.
6. Return the first real node of the left list.

# 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]:
        left, right = ListNode(), ListNode()
        ltail, rtail = left, right

        while head:
            if head.val < x:
                ltail.next = head
                ltail = ltail.next
            else:
                rtail.next = head
                rtail = rtail.next
            head = head.next

        ltail.next = right.next
        rtail.next = None
        return left.next

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

Common Pitfalls

Forgetting to Terminate the Right List

After connecting the left list to the right list, you must set rtail.next = null. Without this, the last node of the right list may still point to a node in the left list from the original structure, creating a cycle and causing infinite loops.

Using Strict Greater Than Instead of Greater or Equal

The partition condition requires nodes with values less than x to come first, and nodes greater than or equal to x to come second. Using > instead of >= for the right partition will incorrectly place nodes equal to x in the left partition.

Not Using Dummy Nodes

Trying to handle the head of each partition manually without dummy nodes leads to complex edge case handling. Using dummy nodes (left and right) as placeholders simplifies the code and eliminates null checks when the first node is encountered for each partition.