Naive Algorithm Steps

1. Initialize two empty arrays: less_than and greater_equal.
2. Traverse the linked list. For each node, check its value.
3. If node.val < x, add the value to the less_than array.
4. Otherwise, add the value to the greater_equal array.
5. Create a completely new linked list by iterating through less_than first, followed by greater_equal, creating a new ListNode for every value.

Pseudo-code

text
function partition(head, x):
    less = []
    greater = []
    current = head
    while current is not null:
        if current.val < x:
            less.add(current.val)
        else:
            greater.add(current.val)
        current = current.next
    
    dummy = new ListNode(0)
    tail = dummy
    for val in less + greater:
        tail.next = new ListNode(val)
        tail = tail.next
    return dummy.next

Complexity & Failure Analysis

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We traverse the list once to extract values and once more to rebuild it.
• Space Complexity: $O(N)$. We store all node values in auxiliary arrays and then create $N$ new node objects.
• Why it is suboptimal: While this solution provides the correct output, it fails to meet the implicit expectation of Linked List problems in technical interviews. The goal is usually to manipulate the pointers of the existing nodes in-place ($O(1)$ space complexity excluding the result structure) rather than allocating memory for entirely new nodes.

Core Insight for Partition List

The most efficient way to solve LeetCode 86 is to recognize that we do not need to perform complex insertions or swaps within a single list, which can get messy with pointer management. Instead, we can decompose the original list into two distinct, temporary linked lists:

1. The "Before" List: Contains all nodes strictly less than x.
2. The "After" List: Contains all nodes greater than or equal to x.

By iterating through the original list exactly once, we can detach nodes from their current position and append them to the tail of either the "Before" or "After" list. Since we process the original list from head to tail, appending to these sub-lists naturally preserves the relative order of elements, satisfying the stability constraint.

Visual Description: Imagine two new "dummy" head nodes rooted in memory. As we traverse the input list, the algorithm acts as a router. If the current node meets the criteria < x, the next pointer of the "Before" list's tail is updated to point to this current node. If the criteria is >= x, the next pointer of the "After" list's tail is updated. Once traversal is complete, we weld the two lists together by setting the next pointer of the "Before" list's tail to the first real node of the "After" list. Finally, we must ensure the "After" list's tail points to null to prevent a circular reference.

Execution Flow

Let's trace the algorithm with Input: head = [1, 4, 3, 2, 5, 2], x = 3.

1. Setup:

   • before_head (dummy) -> before points here.
   • after_head (dummy) -> after points here.
   • Current node: 1.

2. Iteration 1 (Node 1):

   • 1 < 3. Append to before.
   • before list: dummy -> 1.
   • before pointer moves to 1.

3. Iteration 2 (Node 4):

   • 4 >= 3. Append to after.
   • after list: dummy -> 4.
   • after pointer moves to 4.

4. Iteration 3 (Node 3):

   • 3 >= 3. Append to after.
   • after list: dummy -> 4 -> 3.
   • after pointer moves to 3.

5. Iteration 4 (Node 2):

   • 2 < 3. Append to before.
   • before list: dummy -> 1 -> 2.
   • before pointer moves to 2.

6. Iteration 5 (Node 5):

   • 5 >= 3. Append to after.
   • after list: dummy -> 4 -> 3 -> 5.
   • after pointer moves to 5.

7. Iteration 6 (Node 2):

   • 2 < 3. Append to before.
   • before list: dummy -> 1 -> 2 -> 2.
   • before pointer moves to 2.

8. Finalization:

   • End of input list.
   • Connect before tail (2) to after head (4).
   • Set after tail (5) next to null.
   • Result structure: 1 -> 2 -> 2 -> 4 -> 3 -> 5.

Proof of Correctness

The correctness relies on the stable iteration order. Since we traverse the original list from head to tail exactly once:

1. Every node < x is added to the before list in the order it appeared.
2. Every node >= x is added to the after list in the order it appeared.
3. Concatenating before followed by after satisfies the partition requirement.
4. Terminating the after list guarantees a valid, acyclic linked list structure.

Reference Implementation

C++ Solution for LeetCode 86

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode before_head(0);
        ListNode after_head(0);
        
        ListNode* before = &before_head;
        ListNode* after = &after_head;
        
        while (head != nullptr) {
            if (head->val < x) {
                before->next = head;
                before = before->next;
            } else {
                after->next = head;
                after = after->next;
            }
            head = head->next;
        }
        
        // Terminate the 'after' list to prevent cycles
        after->next = nullptr;
        
        // Connect the two lists
        before->next = after_head.next;
        
        return before_head.next;
    }
};

Java Solution for LeetCode 86

java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode beforeHead = new ListNode(0);
        ListNode afterHead = new ListNode(0);
        
        ListNode before = beforeHead;
        ListNode after = afterHead;
        
        while (head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        
        // Important: cut off the end of the 'after' list
        after.next = null;
        
        // Splice the two lists together
        before.next = afterHead.next;
        
        return beforeHead.next;
    }
}

Python Solution for LeetCode 86

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]:
        before_head = ListNode(0)
        after_head = ListNode(0)
        
        before = before_head
        after = after_head
        
        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next
            
        # Prevent cycle by ensuring the last node points to None
        after.next = None
        
        # Merge the two lists
        before.next = after_head.next
        
        return before_head.next