Skip to content
RED SAGSkills
medium30 ptslinked-list

Split a List Around a Pivot

A singly linked list is given as an array values (head first) together with a pivot x.

Rearrange the list so that every node with a value less than x comes before every node with a value greater than or equal to x. Inside each of the two groups the nodes must keep their original relative order. Return the rearranged list as an array.

On real nodes this is done by building two chains and joining them, without allocating new nodes.

Example 1

Input: values = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: 1, 2, 2 are below 3 and keep their order; 4, 3, 5 follow.

Example 2

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

Constraints

  • 0 <= values.length <= 3 * 10^4
  • -1000 <= values[i], x <= 1000
Hint 1

Keep two chains: one for small values and one for the rest.

Hint 2

Append each node to the end of its chain, then link the end of the first chain to the start of the second.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Full Stack Developer, Embedded Systems Engineer, Data Engineer, Database Administrator

Run checks your code on 2 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.