138. Partition List

Medium · Linked List

Given a linked list and a value x, partition the list such that all nodes with values less than x come before nodes with values greater than or equal to x. You should preserve the original relative order within each partition.

The input is an array representation of a linked list, where each element is a node value. Return the partitioned list as an array.

Examples

Example 1
Input: list = [1, 4, 3, 2, 5, 2], x = 3
Output: [1, 2, 2, 4, 3, 5]
Explanation: Nodes with values < 3 are [1, 2, 2] and nodes with values >= 3 are [4, 3, 5]. We preserve the relative order within each partition: 1 comes before 2s, and 4 comes before 3 which comes before 5.
Example 2
Input: list = [5, 4, 3, 2, 1], x = 3
Output: [1, 2, 5, 4, 3]
Explanation: Nodes < 3 are [1, 2] in their original order. Nodes >= 3 are [5, 4, 3] in their original order.

Constraints