LeetCode 86: Partition List Solution in Python Explained

Problem Statement

In LeetCode 86, you’re given the head of a linked list and an integer x. Your task is to partition the list such that all nodes with values less than x appear before all nodes with values greater than or equal to x, maintaining the original relative order within each partition. This is distinct from problems like LeetCode 83: Remove Duplicates from Sorted List, as it’s about reordering, not removing.

Constraints

• Number of nodes: 0 <= n <= 200
• Node values: -100 <= Node.val <= 100
• Partition value: -100 <= x <= 100

Example

Let’s see some cases:

Copy codeInput: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: Nodes < 3 (1,2,2) come before nodes >= 3 (4,3,5), order preserved.

Copy codeInput: head = [2,1], x = 2
Output: [1,2]
Explanation: 1 < 2 comes before 2 >= 2.

Copy codeInput: head = [1,1], x = 2
Output: [1,1]
Explanation: Both < 2, no change needed.

These examples show the goal: split and reorder around x.

Understanding the Problem

How do you solve LeetCode 86: Partition List in Python? Take head = [1,4,3,2,5,2], x = 3. We need [1,2,2] (less than 3) before [4,3,5] (greater than or equal to 3), keeping each group’s order. This isn’t a search like LeetCode 1: Two Sum; it’s about list partitioning. We’ll use: 1. Two Dummy Lists: O(n) time, O(1) space—our top choice. 2. In-Place: O(n) time, O(1) space—a trickier option.

Let’s start with the primary solution.

Solution 1: Two Dummy Lists Approach (Primary)

Explanation

We create two separate lists using dummy nodes: one for nodes less than x and one for nodes greater than or equal to x. Traverse the original list, appending each node to the appropriate dummy list, then connect the two lists. This ensures stable ordering within each partition.

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

• Less than 3: [1,2,2].
• Greater than or equal: [4,3,5].
• Combine: [1,2,2,4,3,5].

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next.

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

Goal: Return [1,2,2,4,3,5].

• Start: before_dummy = ListNode(0), after_dummy = ListNode(0), before = before_dummy, after = after_dummy, curr = head.
• Step 1: curr.val = 1 < 3.
• before.next = curr → before_dummy.next = 1.
• before = 1, curr = 4.
• Step 2: curr.val = 4 >= 3.
• after.next = 4, after = 4, curr = 3.
• Step 3: curr.val = 3 >= 3.
• after.next = 3, after = 3, curr = 2.
• Step 4: curr.val = 2 < 3.
• before.next = 2, before = 2, curr = 5.
• Step 5: curr.val = 5 >= 3.
• after.next = 5, after = 5, curr = 2.
• Step 6: curr.val = 2 < 3.
• before.next = 2, before = 2, curr = None.
• Step 7: Connect: before.next = after_dummy.next (2 -> 4), after.next = None.
• Finish: before_dummy.next = [1,2,2,4,3,5], return it.

Example 2: head = [2,1], x = 2

Goal: Return [1,2].

• Start: before = before_dummy, after = after_dummy, curr = 2.
• Step 1: curr.val = 2 >= 2.
• after.next = 2, after = 2, curr = 1.
• Step 2: curr.val = 1 < 2.
• before.next = 1, before = 1, curr = None.
• Step 3: Connect: before.next = 2, after.next = None.
• Finish: [1,2].

Example 3: head = [1,1], x = 2

Goal: Return [1,1].

• Start: before = before_dummy, after = after_dummy, curr = 1.
• Step 1: curr.val = 1 < 2.
• before.next = 1, before = 1, curr = 1.
• Step 2: curr.val = 1 < 2.
• before.next = 1, before = 1, curr = None.
• Step 3: Connect: before.next = None, after.next = None.
• Finish: [1,1].

How the Code Works (Two Dummy Lists) – Detailed Line-by-Line Explanation

Here’s the Python code with a meticulous breakdown:

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def partition(head: ListNode, x: int) -> ListNode:
    # Line 1: Create dummy nodes for two lists
    before_dummy = ListNode(0)
    after_dummy = ListNode(0)
    # Two dummy nodes (val = 0, next = None) act as heads for the less-than and greater-than-or-equal lists
    # Simplifies linking without worrying about the actual head

    # Line 2: Initialize pointers for both lists
    before = before_dummy
    after = after_dummy
    # before and after start at their respective dummies
    # Will move to append nodes to each list

    # Line 3: Initialize curr to traverse the original list
    curr = head
    # curr starts at the head of the input list (e.g., 1 in [1,4,3,2,5,2])

    # Line 4: Traverse the list while curr exists
    while curr:
        # Loops until curr is None (end of list)
        # Processes each node to place it in the correct partition

        # Line 5: Check if current node’s value is less than x
        if curr.val < x:
            # If true (e.g., 1 < 3), node belongs in the before list

            # Line 6: Append node to before list
            before.next = curr
            # Links the current node to the before pointer (e.g., before_dummy.next = 1)

            # Line 7: Move before pointer forward
            before = before.next
            # Advances before to the newly added node (e.g., before = 1)
            # Prepares to append the next less-than node
        else:
            # If curr.val >= x (e.g., 4 >= 3), node belongs in the after list

            # Line 8: Append node to after list
            after.next = curr
            # Links the current node to the after pointer (e.g., after_dummy.next = 4)

            # Line 9: Move after pointer forward
            after = after.next
            # Advances after to the newly added node (e.g., after = 4)

        # Line 10: Move curr to the next node
        curr = curr.next
        # Advances curr to process the next node (e.g., from 1 to 4)
        # Note: We don’t alter curr.next here, just move our reference

    # Line 11: Connect the before list to the after list
    before.next = after_dummy.next
    # Links the end of the before list to the start of the after list
    # e.g., last node 2 in [1,2,2] connects to 4 in [4,3,5]

    # Line 12: Ensure the after list ends properly
    after.next = None
    # Sets the next pointer of the last node in after list to None
    # Prevents any dangling references (e.g., 5.next = None)

    # Line 13: Return the partitioned list
    return before_dummy.next
    # Returns the head of the combined list (e.g., [1,2,2,4,3,5])
    # Skips the dummy node to give the actual start

This granular explanation ensures every step is clear for beginners.

Alternative: In-Place Approach

Explanation

Traverse the list, moving nodes less than x to the front while maintaining order, using pointers to track partitions without extra lists. This is trickier but saves space.

For [1,4,3,2,5,2], x = 3:

• Move 1, 2, 2 forward, leave 4, 3, 5.

Step-by-Step Example (Alternative)

For [1,4,3,2,5,2], x = 3:

• Start: head = 1.
• Step 1: 1 < 3, keep at front.
• Step 2: 4 >= 3, skip.
• Step 3: 3 >= 3, skip.
• Step 4: 2 < 3, move before 4.
• Step 5: 5 >= 3, skip.
• Step 6: 2 < 3, move before 4.
• Finish: [1,2,2,4,3,5].

How the Code Works (In-Place)

Copy codedef partitionInPlace(head: ListNode, x: int) -> ListNode:
    if not head or not head.next:
        return head
    dummy = ListNode(0, head)
    prev = dummy
    curr = head
    while curr and curr.val < x:
        prev = curr
        curr = curr.next
    while curr:
        if curr.val < x:
            prev.next = curr.next
            curr.next = prev.next
            prev.next = curr
            curr = prev.next.next
            prev = prev.next
        else:
            curr = curr.next
    return dummy.next

Complexity

• Two Dummy Lists:
• Time: O(n) – single pass.
• Space: O(1) – only pointers.
• In-Place:
• Time: O(n) – single pass.
• Space: O(1) – no extra lists.

Efficiency Notes

Two Dummy Lists is clearer and easier to implement, while In-Place saves space but is more complex—both are O(n) time, making Two Dummy Lists the preferred choice for its readability.

Key Insights

• Dummy Nodes: Simplify partitioning.
• Stable Order: Preserve relative positions.
• Two Groups: Split around x.

Additional Example

For head = [3,1,2], x = 3:

• Goal: [1,2,3].
• Two Dummy: [1,2] < 3, [3] >= 3 → [1,2,3].

Edge Cases

• Empty List: [] → [].
• Single Node: [1] → [1].
• All Less: [1,2] < 3 → [1,2].

Both solutions handle these smoothly.

Final Thoughts

LeetCode 86: Partition List in Python is a neat linked list challenge. The Two Dummy Lists solution is intuitive and efficient, while In-Place offers a space-savvy twist. Want more? Try LeetCode 82 for duplicate removal or LeetCode 206: Reverse Linked List for list flipping. Ready to practice? Solve LeetCode 86 on LeetCode with [1,4,3,2,5,2] and x = 3, aiming for [1,2,2,4,3,5]—test your skills now!