Loading problems...
TL;DR: The optimal LeetCode 86 solution creates two separate linked lists—one for elements less than x and one for elements greater than or equal to x—using dummy heads, then concatenates them to form the result.
The Partition List problem asks us to rearrange a linked list based on a specific value x. We must move all nodes with values strictly less than x to the front of the list, while keeping all nodes with values greater than or equal to x at the back. A critical constraint is that the relative order of the nodes in each partition must be preserved. This means if node A appears before node B in the original list and both are in the same partition (e.g., both are less than x), node A must still appear before node B in the result.
This is a popular interview question because it tests pointer manipulation skills and the ability to modify data structures in-place without using additional memory for data storage.
A naive or brute force approach typically involves extracting the data from the linked list to process it in a more convenient format, such as an array or a dynamic list (like an in Java or in C++).
ArrayListvectorless_than and greater_equal.node.val < x, add the value to the less_than array.greater_equal array.less_than first, followed by greater_equal, creating a new ListNode for every value.textfunction 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
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:
x.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.

Let's trace the algorithm with Input: head = [1, 4, 3, 2, 5, 2], x = 3.
Setup:
before_head (dummy) -> before points here.after_head (dummy) -> after points here.1.Iteration 1 (Node 1):
1 < 3. Append to before.before list: dummy -> 1.before pointer moves to 1.Iteration 2 (Node 4):
4 >= 3. Append to after.after list: dummy -> 4.after pointer moves to 4.Iteration 3 (Node 3):
3 >= 3. Append to after.after list: dummy -> 4 -> 3.after pointer moves to 3.Iteration 4 (Node 2):
2 < 3. Append to before.before list: dummy -> 1 -> 2.before pointer moves to 2.Iteration 5 (Node 5):
5 >= 3. Append to after.after list: dummy -> 4 -> 3 -> 5.after pointer moves to 5.Iteration 6 (Node 2):
2 < 3. Append to before.before list: dummy -> 1 -> 2 -> 2.before pointer moves to 2.Finalization:
before tail (2) to after head (4).after tail (5) next to null.1 -> 2 -> 2 -> 4 -> 3 -> 5.The correctness relies on the stable iteration order. Since we traverse the original list from head to tail exactly once:
< x is added to the before list in the order it appeared.>= x is added to the after list in the order it appeared.before followed by after satisfies the partition requirement.after list guarantees a valid, acyclic linked list structure.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/** * 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# 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
before_head, after_head, before, after) and do not create new nodes or use recursion stacks. The rearrangement is done in-place by rewiring existing nodes.The Reordering / Partitioning subpattern is fundamental for linked list problems involving structural changes. The following problems share similar logic:
Why do I get a Memory Limit Exceeded or Time Limit Exceeded?
after.next = null (or None) at the end of the operation.after list likely still points to a node that was moved to the before list. This creates a cycle. When the system tries to print or traverse the result, it loops infinitely.Why is my output list missing nodes?
head or losing the reference to the dummy heads during traversal.before_head = before_head.next) instead of a separate runner pointer (before), you lose the anchor to the start of the list.Why is my partition unstable (order changed)?