Skip to main content
Talentd

Partition List - Solution & Explanation

MediumLinked ListTwo Pointers18 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

 

Example 1:

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

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

 

Constraints:

  • The number of nodes in the list is in the range [0, 200].
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

Approach Overview

Problem Overview: Given the head of a linked list and an integer x, rearrange the nodes so that all nodes with values less than x appear before nodes greater than or equal to x. The relative order of nodes in each partition must remain the same.

Approach 1: Two-Pointer Partition Lists (O(n) time, O(1) extra space)

This approach builds two temporary chains while traversing the list once. One list stores nodes with values < x, and the other stores nodes with values >= x. Use two pointers (usually dummy heads) to append nodes as you iterate through the original list. After processing all nodes, connect the end of the smaller list to the head of the larger list. The key insight is that you never create new nodes—you only rewire next pointers—so the relative order inside each partition stays intact. This technique is a classic application of linked list manipulation combined with the two pointers pattern.

Approach 2: In-Place Rearrangement (O(n) time, O(1) space)

Instead of maintaining two separate lists, this method reorganizes nodes directly inside the existing structure. Track the tail of the "less than x" region while scanning the list. When a node with value < x appears after larger elements, detach it and move it right after the partition boundary. Pointer updates must be handled carefully to avoid breaking the list. The advantage is strict constant extra space with no additional dummy lists. This version emphasizes pointer operations and deeper understanding of linked list structure.

Recommended for interviews: The two-pointer partition list method is what most interviewers expect. It is simple, safe, and easy to reason about while maintaining stable ordering. The in-place rearrangement approach demonstrates stronger pointer manipulation skills and can impress interviewers if implemented cleanly. Showing the straightforward partition first proves correctness; discussing the in-place optimization shows deeper mastery of two pointer and linked list techniques.

Approach 1: Two-Pointer Approach

This approach involves using two separate linked lists to store nodes that are less than x and nodes that are greater than or equal to x. You traverse the original list and attach each node to the appropriate list. Finally, you connect the two lists together to form the partitioned list.

This C implementation uses two dummy node pointers to build the 'less than x' and 'greater or equal to x' lists. It iterates through the original list only once, making the approach efficient.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), as we only use a constant amount of extra space.

Try this approach in the editor →

Approach 2: In-Place Rearrangement Approach

This in-place rearrangement technique modifies the original list without the need of additional dummy nodes. This is accomplished by managing pointers to redefine segment connections efficiently.

This C implementation uses four pointers to represent the start and end of the 'before' and 'after' lists. As we traverse the original list, we reattach nodes to these lists, eventually connecting them at the end.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Simulation

We create two linked lists l and r, one to store nodes less than x and the other to store nodes greater than or equal to x. Then we concatenate them.

The time complexity is O(n), where n is the length of the original linked list. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Approach

Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), as we only use a constant amount of extra space.

In-Place Rearrangement Approach

Time Complexity: O(n)
Space Complexity: O(1)

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer Partition ListsO(n)O(1)Best general solution. Clean logic using two dummy heads and stable ordering.
In-Place RearrangementO(n)O(1)When minimizing auxiliary structures and demonstrating advanced pointer manipulation.

Video Solution

Partition List - Linked List - Leetcode 86 • NeetCode • 46,878 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Partition List easy or hard?
Partition List is considered a medium difficulty problem. The traversal itself is straightforward, but maintaining stable order while correctly updating pointers can be tricky for beginners working with linked lists.
How to solve Partition List in O(n)?
Iterate through the linked list once while maintaining two pointers representing the tails of two partitions: values less than x and values greater than or equal to x. Append each node to the appropriate list as you scan. After traversal, connect the smaller partition's tail to the head of the larger partition. This single pass guarantees O(n) time complexity.
What is the best approach for Partition List?
The two-pointer partition approach is the most common solution. Traverse the linked list once while building two chains: nodes less than x and nodes greater than or equal to x. Connect the two lists at the end. This runs in O(n) time and O(1) extra space while preserving the relative order of nodes.
What data structure is used in Partition List?
The problem operates entirely on a singly linked list. The solution relies on pointer manipulation, often with dummy head nodes and two pointer references to maintain partitions during traversal.
What is the time complexity of Partition List?
Partition List runs in O(n) time because each node in the linked list is visited exactly once. Pointer updates and comparisons are constant-time operations. Space complexity is O(1) since the algorithm only uses a few pointer references and does not allocate additional data structures proportional to input size.
Partition List Python or Java solution approach?
Python and Java solutions typically implement the two-pointer partition strategy. Create two dummy nodes for the 'less than x' and 'greater or equal to x' lists, iterate through the original list, attach nodes to the correct partition, and finally link the lists together.
Is Partition List asked at Google, Amazon, or Meta?
Partition List is a common linked list partitioning problem frequently seen in interviews at companies like Amazon, Google, and Meta. Variants of the problem appear in technical screens because they test pointer manipulation, stable ordering, and understanding of linked list traversal.

Ready to solve this problem?

Practice Partition List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Partition Array According to Given Pivot