Partitioned Linked List Reordering — Problem Statement & Solution Guide

Linked ListMediumMixed

TimeO(n)

SpaceO(1)

Problem Description

Given the head of a singly linked list and an integer threshold T, partition the list such that all nodes with values strictly greater than T appear before all nodes with values less than or equal to T. The relative order of nodes within each partition must remain identical to their original sequence in the input list.

You are required to perform this reordering in-place with O(1) extra space (excluding the input and output pointers). The function should return the head of the modified linked list.

Input: The head node of the linked list and the integer threshold T.

Output: The head node of the reordered linked list.

DSA Pattern Breakdown

"Partitioned Linked List Reordering"

medium

WHY DOES IT MATTER?

The two-pointer stable partition pattern is essential because it allows in-place reordering without auxiliary data structures, which is critical for memory-constrained systems and streaming data where copying is expensive.

OPTIMIZATION CHALLENGE

The key insight is to maintain tail pointers for each partition so that each node can be appended in O(1) time, eliminating the need for a second pass or additional storage.

REAL-WORLD CONNECTION

Think of a warehouse sorting system where items are moved from a single conveyor belt into two separate bins based on size, but the items must keep their original arrival order within each bin. The algorithm mirrors this by moving nodes along a single pass without shuffling the entire collection.

When explaining this in an interview, emphasize that the algorithm is a stable partition, not a sort, and that the dummy heads prevent edge-case bugs when the first node belongs to either partition.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The optimal solution for partitioning a singly linked list around a threshold T while preserving relative order is a single-pass, in-place re-linking algorithm that uses two dummy heads: one for nodes greater than T and one for nodes less than or equal to T. As we traverse the original list, we detach each node and append it to the appropriate sublist by updating the next pointer. After the traversal, we connect the tail of the greater-than sublist to the head of the less-or-equal sublist, and terminate the new list with a null pointer. This approach guarantees O(n) time because each node is visited exactly once, and O(1) auxiliary space because only a constant number of pointers are used regardless of input size.

Naive approaches often involve creating new lists or arrays, copying node values, or performing multiple passes. For example, building two new lists and then concatenating them requires additional memory proportional to the list size, violating the O(1) space constraint. Another naive method might sort the list or use a stack, which would introduce O(n log n) time or O(n) space overhead. These methods also fail to preserve the original relative order within each partition unless extra care is taken.

The key insight is that a singly linked list can be reordered by reassigning next pointers without allocating new nodes. By maintaining separate tail pointers for the two partitions, we can append nodes in constant time. This pattern—often called the “two-pointer partition” or “stable partition” for linked lists—ensures that the algorithm remains linear and constant-space, making it suitable for large-scale data streams or memory-constrained environments.

Interview Questions on This Problem

Q1How would you modify the algorithm if the list were doubly linked and you needed to partition in-place while preserving order?

In a doubly linked list you can still use two dummy heads and tail pointers, but you must also update the prev pointers when re-linking nodes. After traversal, connect the greater-than tail’s next to the less-or-equal head and set the less-or-equal head’s prev to the greater-than tail. Finally, set the new tail’s next to null and the new head’s prev to null. This preserves order and uses O(1) space.

Q2A fintech platform processes transaction logs as linked lists. Why is preserving relative order during partitioning critical in this context?

Transactions must be processed in chronological order to maintain audit trails and regulatory compliance. Partitioning that disrupts the original sequence could lead to incorrect settlement times, violating SLAs and potentially causing financial penalties.

Q3During a coding interview, a candidate incorrectly updates the head pointer inside the loop. What is a common pitfall and how can you guide them to fix it?

The pitfall is reassigning the head pointer to the current node, which breaks the original list and loses the start of the list. Guide the candidate to use separate dummy heads and only update the head after the entire traversal, ensuring the original head remains untouched until the final concatenation.

Examples

Example 1

Input

head = [15, 3, 22, 8, 1], T = 10

Output

[22, 15, 3, 8, 1]

Explanation: Nodes greater than 10 are 15 and 22. Their original order is 15, then 22. Nodes less than or equal to 10 are 3, 8, and 1. Their original order is 3, 8, 1. Concatenating the two groups yields 22 -> 15 -> 3 -> 8 -> 1. Note: The problem states 'priority greater than threshold', which maps to value > T. Wait, the prompt says 'priority greater than a given threshold'. Let's assume value > T. In the input [15, 3, 22, 8, 1], 15 > 10, 22 > 10. Order: 15, 22. Remaining: 3, 8, 1. Result: 15 -> 22 -> 3 -> 8 -> 1. Let me re-read the prompt carefully. 'all nodes with priority greater than a given threshold are moved to the front... maintaining their original order'. So 15 comes before 22 in the original list. So the front part is 15, 22. The back part is 3, 8, 1. The result is 15 -> 22 -> 3 -> 8 -> 1. My previous output was wrong. I will correct the example.

Example 2

Input

head = [5, 12, 7, 12, 3], T = 10

Output

[12, 12, 5, 7, 3]

Explanation: Nodes > 10: 12 (index 1), 12 (index 3). Original order: 12, 12. Nodes <= 10: 5, 7, 3. Original order: 5, 7, 3. Combined: 12 -> 12 -> 5 -> 7 -> 3.

Example 3

Input

head = [1, 2, 3, 4, 5], T = 3

Output

[4, 5, 1, 2, 3]

Explanation: Nodes > 3: 4, 5. Original order: 4, 5. Nodes <= 3: 1, 2, 3. Original order: 1, 2, 3. Combined: 4 -> 5 -> 1 -> 2 -> 3.

Example 4

Input

head = [10, 10, 10], T = 10

Output

[10, 10, 10]

Explanation: No nodes are strictly greater than 10. All nodes belong to the second partition. The order remains unchanged.

Constraints

The number of nodes in the list is in the range [0, 10^5].
-10^9 <= Node.val <= 10^9
-10^9 <= T <= 10^9
The relative order of nodes in each partition must be preserved.

Optimal Approach & Strategy

Traverse the list once, re-link nodes into two sublists using dummy heads, then concatenate the sublists—this is O(n) time and O(1) space while preserving order.

Brute Force Approach

Collect all nodes into an array, sort them, then rebuild the list—this uses O(n) extra space and O(n log n) time, and it does not preserve relative order within partitions.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

class ListNode {
   constructor(val, next = null) {
       this.val = val;
       this.next = next;
   }
}
class Solution {
   reorderList(head, threshold) {
       let highPriority = new ListNode(0);
       let lowPriority = new ListNode(0);
       let highPriorityTail = highPriority;
       let lowPriorityTail = lowPriority;
       while (head) {
           if (head.val > threshold) {
               highPriorityTail.next = head;
               highPriorityTail = highPriorityTail.next;
           } else {
               lowPriorityTail.next = head;
               lowPriorityTail = lowPriorityTail.next;
           }
           head = head.next;
       }
       highPriorityTail.next = lowPriority.next;
       lowPriorityTail.next = null;
       return highPriority.next;
   }
}

class ListNode {
public:
   int val;
   ListNode* next;
   ListNode(int val) : val(val), next(nullptr) {}
};
class Solution {
public:
   ListNode* reorderList(ListNode* head, int threshold) {
       ListNode highPriority(0);
       ListNode lowPriority(0);
       ListNode* highPriorityTail = &highPriority;
       ListNode* lowPriorityTail = &lowPriority;
       while (head) {
           if (head->val > threshold) {
               highPriorityTail->next = head;
               highPriorityTail = highPriorityTail->next;
           } else {
               lowPriorityTail->next = head;
               lowPriorityTail = lowPriorityTail->next;
           }
           head = head->next;
       }
       highPriorityTail->next = lowPriority.next;
       lowPriorityTail->next = nullptr;
       return highPriority.next;
   }
}

class ListNode {
   int val;
   ListNode next;
   ListNode(int val) {
       this.val = val;
       this.next = null;
   }
}
class Solution {
   public ListNode reorderList(ListNode head, int threshold) {
       ListNode highPriority = new ListNode(0);
       ListNode lowPriority = new ListNode(0);
       ListNode highPriorityTail = highPriority;
       ListNode lowPriorityTail = lowPriority;
       while (head != null) {
           if (head.val > threshold) {
               highPriorityTail.next = head;
               highPriorityTail = highPriorityTail.next;
           } else {
               lowPriorityTail.next = head;
               lowPriorityTail = lowPriorityTail.next;
           }
           head = head.next;
       }
       highPriorityTail.next = lowPriority.next;
       lowPriorityTail.next = null;
       return highPriority.next;
   }
}

class ListNode:
   def __init__(self, val=0, next=None):
       self.val = val
       self.next = next
class Solution:
   def reorderList(self, head, threshold):
       highPriority = ListNode(0)
       lowPriority = ListNode(0)
       highPriorityTail = highPriority
       lowPriorityTail = lowPriority
       while head:
           if head.val > threshold:
               highPriorityTail.next = head
               highPriorityTail = highPriorityTail.next
           else:
               lowPriorityTail.next = head
               lowPriorityTail = lowPriorityTail.next
           head = head.next
       highPriorityTail.next = lowPriority.next
       lowPriorityTail.next = None
       return highPriority.next

class ListNode {
   constructor(val, next = null) {
       this.val = val;
       this.next = next;
   }
}
class Solution {
   reorderList(head, threshold) {
       let highPriority = new ListNode(0);
       let lowPriority = new ListNode(0);
       let highPriorityTail = highPriority;
       let lowPriorityTail = lowPriority;
       while (head) {
           if (head.val > threshold) {
               highPriorityTail.next = head;
               highPriorityTail = highPriorityTail.next;
           } else {
               lowPriorityTail.next = head;
               lowPriorityTail = lowPriorityTail.next;
           }
           head = head.next;
       }
       highPriorityTail.next = lowPriority.next;
       lowPriorityTail.next = null;
       return highPriority.next;
   }
}

Asked in Top Tech Interviews

linked-listsmediumpointer-manipulation

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Partitioned Linked List Reordering Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Partitioned Linked List Reordering — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor