86. Partition List
Partition List (LeetCode 86) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.
How to solve Partition List
Partition List is a Linked List Reordering and Partitioning problem, part of Linked List Manipulation Patterns. Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.
Work towards the solution in these steps:
- Consider how you might rearrange nodes in a linked list without creating new nodes or losing existing ones.
- Think about splitting the list into two separate lists: one for nodes less than x and one for nodes greater or equal to x.
- How can you maintain the relative order of nodes within each partition while traversing the original list?
The reference solution runs in O(n) time and O(n) space.
The Partition List solution and editorial walks through the full approach with reference code.
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
Topics and companies
Topics: Linked List, Two Pointers.
Reported in interviews at Microsoft, Amazon, Apple, Bloomberg, Facebook.
How to practise Partition List on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Partition List in the code editor, or read the Partition List editorial for a worked solution with its approach and complexity analysis.
Where Partition List sits in the DSA pattern sheet
- Linked List Manipulation Patterns pattern guide
- Reordering / Partitioning subpattern
- The full DSA patterns sheet
Problems related to Partition List
Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:
- Insert Greatest Common Divisors in Linked List — Medium, same subpattern
- Odd Even Linked List — Medium, same subpattern
- Reorder List — Medium, same subpattern
- Rotate List — Medium, same subpattern
- Swap Nodes in Pairs — Medium, same subpattern
- Add Two Numbers — Medium, same pattern
Partition List FAQ
What is the LeetCode number of Partition List?
Partition List is LeetCode problem 86, rated Medium.
What pattern is used to solve Partition List?
Partition List is a Linked List Reordering and Partitioning problem. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.
What is the time complexity of Partition List?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Partition List?
Partition List has been reported in interviews at Microsoft, Amazon, Apple, Bloomberg, Facebook.