Partition List

Partition List 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.

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), where n is the number of elements in the input vector. We traverse the list once to partition, and concatenation is also O(n). time and O(n), as we use two additional vectors to store the partitions before combining them. 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
• All coding practice problems

Problems related to Partition List

Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:

• 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
• Intersection of Two Linked Lists — Easy, same pattern