Problem Description

You are given the head of a linked list and an integer value x. Your task is to rearrange the linked list so that all nodes with values less than x appear before all nodes with values greater than or equal to x.

The key requirements are:

• Nodes with values < x should come first
• Nodes with values ≥ x should come after
• The relative order within each group must be preserved

For example, if you have a linked list 1 -> 4 -> 3 -> 2 -> 5 -> 2 and x = 3:

• Nodes less than 3: 1 -> 2 -> 2 (maintaining their original order)
• Nodes greater than or equal to 3: 4 -> 3 -> 5 (maintaining their original order)
• Result: 1 -> 2 -> 2 -> 4 -> 3 -> 5

The solution creates two separate linked lists:

• One list l collects all nodes with values less than x
• Another list r collects all nodes with values greater than or equal to x

As we traverse the original linked list, we append each node to the appropriate list based on its value. Finally, we connect the tail of the "less than" list to the head of the "greater than or equal" list to form the partitioned result.

The code uses dummy head nodes (l and r) to simplify the list construction, and maintains tail pointers (tl and tr) to efficiently append nodes to each list. The line tr.next = None ensures the last node doesn't point to any remaining nodes from the original list, and tl.next = r.next connects the two partitions together.

Intuition

When we need to partition elements based on a value while maintaining relative order, the natural approach is to think about grouping. Imagine you're sorting mail into two bins - one for local addresses and one for out-of-state addresses, but you need to keep the order in which the mail arrived within each bin.

The key insight is that we don't need to modify the original linked list in place, which would be complex and require careful pointer manipulation. Instead, we can build the result by distributing nodes into two separate chains as we traverse the original list.

Think of it like having two queues at a theme park - one for regular visitors and one for VIP pass holders. As people arrive, they join the appropriate queue based on their ticket type, maintaining their arrival order within each queue. At the end, we simply connect the regular queue to the VIP queue.

This leads us to the two-pointer approach:

1. Create two separate chains - one for nodes with values < x and another for values ≥ x
2. As we traverse the original list, append each node to the appropriate chain
3. Connect the two chains at the end

Using dummy head nodes simplifies the implementation because we don't need special handling for the first node in each chain. The tail pointers (tl and tr) allow us to efficiently append nodes in O(1) time without having to traverse to the end of each chain repeatedly.

The elegance of this solution lies in its simplicity - we're essentially doing a stable partition by physically separating the nodes into two groups and then joining them, rather than trying to rearrange pointers within a single list structure.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The implementation uses a simulation approach with two separate linked lists to partition the nodes. Here's how the algorithm works step by step:

1. Initialize Two Dummy Nodes:

l = ListNode()  # Dummy head for nodes < x
r = ListNode()  # Dummy head for nodes >= x

We create two dummy nodes to serve as the heads of our two partition lists. These dummy nodes simplify list construction by eliminating edge cases for empty lists.

2. Set Up Tail Pointers:

tl, tr = l, r

We maintain tail pointers for both lists. These pointers always point to the last node in each partition, allowing us to append new nodes in O(1) time.

3. Traverse and Distribute Nodes:

while head:
    if head.val < x:
        tl.next = head
        tl = tl.next
    else:
        tr.next = head
        tr = tr.next
    head = head.next

For each node in the original list:

• If the node's value is less than x, append it to the "less than" list by connecting it to tl.next and advancing tl
• Otherwise, append it to the "greater than or equal" list by connecting it to tr.next and advancing tr
• Move to the next node in the original list

4. Clean Up and Connect:

tr.next = None  # Terminate the right list
tl.next = r.next  # Connect left list to right list

• Set tr.next = None to ensure the last node of the "greater than or equal" list doesn't point to any remaining nodes from the original list
• Connect the tail of the "less than" list to the first actual node of the "greater than or equal" list (skipping the dummy node with r.next)

5. Return the Result:

return l.next

Return l.next to skip the dummy node and start from the first actual node of the partitioned list.

Time Complexity: O(n) where n is the number of nodes, as we traverse the list once.

Space Complexity: O(1) as we only use a constant amount of extra space for pointers. We're reusing the existing nodes rather than creating new ones.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: Linked list: 3 -> 1 -> 2, x = 2

Step 1: Initialize dummy nodes and tail pointers

l (dummy) -> null     [for nodes < 2]
tl points to l

r (dummy) -> null     [for nodes >= 2]
tr points to r

head points to 3

Step 2: Process first node (value = 3)

• Since 3 >= 2, append to right list
• tr.next = node(3), then tr = node(3)

l (dummy) -> null
tl still points to l

r (dummy) -> 3 -> 1 -> 2
tr now points to node(3)

head moves to node(1)

Step 3: Process second node (value = 1)

• Since 1 < 2, append to left list
• tl.next = node(1), then tl = node(1)

l (dummy) -> 1 -> 2
tl now points to node(1)

r (dummy) -> 3 -> 1 -> 2
tr still points to node(3)

head moves to node(2)

Step 4: Process third node (value = 2)

• Since 2 >= 2, append to right list
• tr.next = node(2), then tr = node(2)

l (dummy) -> 1 -> 2
tl still points to node(1)

r (dummy) -> 3 -> 2
tr now points to node(2)

head becomes null (end of list)

Step 5: Clean up and connect

• Set tr.next = null to terminate right list
• Connect lists: tl.next = r.next (connects node(1) to node(3))

l (dummy) -> 1 -> 3 -> 2 -> null

Step 6: Return result

• Return l.next which points to node(1)

Final Result: 1 -> 3 -> 2

The partition is complete: node with value 1 (< 2) comes first, followed by nodes with values 3 and 2 (>= 2), maintaining their original relative order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the original linked list. The algorithm traverses the entire linked list exactly once in the while loop, performing constant-time operations (comparisons and pointer assignments) for each node.

Space Complexity: O(1). Although the code creates two dummy nodes (l and r) and uses four pointer variables (tl, tr, l, r), these occupy a constant amount of extra space regardless of the input size. The algorithm modifies the existing nodes by rearranging their pointers rather than creating new nodes, so no additional space proportional to the input size is required.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Forgetting to Set the Last Node's Next Pointer to None

The Problem: One of the most critical yet easily overlooked steps is setting right_tail.next = None after distributing all nodes. Without this line, the last node in the right partition might still point to nodes from the original linked list, creating either:

1. A cycle - if the last node points back to an earlier node that's now part of one of the partitions
2. Incorrect nodes - if the last node points to nodes that shouldn't be in the final result

Example of the Bug: Consider the list 1 -> 4 -> 3 -> 2 -> 5 -> 2 with x = 3:

• After processing, we have:
  • Left list: 1 -> 2 -> 2
  • Right list: 4 -> 3 -> 5
• The node with value 5 was originally pointing to the second 2 node
• Without setting right_tail.next = None, the result would be: 1 -> 2 -> 2 -> 4 -> 3 -> 5 -> 2 -> ... (potentially creating a cycle)

The Solution: Always terminate the right partition explicitly:

# CRITICAL: Must set this to None to avoid cycles or extra nodes
right_tail.next = None

# Then connect the partitions
left_tail.next = right_dummy.next

Alternative Approach to Avoid This Pitfall: Create new nodes instead of reusing existing ones (though this uses O(n) extra space):

def partition_safe(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
    left_dummy = ListNode()
    right_dummy = ListNode()
    left_tail = left_dummy
    right_tail = right_dummy
  
    while head:
        # Create new nodes to avoid pointer issues
        new_node = ListNode(head.val)
      
        if head.val < x:
            left_tail.next = new_node
            left_tail = left_tail.next
        else:
            right_tail.next = new_node
            right_tail = right_tail.next
      
        head = head.next
  
    # No need to set right_tail.next = None since new nodes have None by default
    left_tail.next = right_dummy.next
    return left_dummy.next

Key Takeaway: When manipulating linked list pointers by reusing existing nodes, always be mindful of what the original next pointers are pointing to. Explicitly terminate lists to prevent unintended connections.