Split a List Around a Pivot

Medium

You are given a singly linked list head and an integer pivot. Rearrange the nodes so that every node with a value less than pivot comes before every node with a value greater than or equal to pivot. Within each of the two groups, nodes must keep their original relative order. Return the head of the resulting list. An empty list stays empty.

Example 1

head=list_node([6, 2, 9, 1, 5]), pivot=5 → [2, 1, 6, 9, 5]

Only 2 and 1 are below 5; they come first in their original order, followed by 6, 9, 5, also in their original order.

Example 2

head=list_node([-3, 4, -3]), pivot=0 → [-3, -3, 4]

Both −3 values are below zero and move to the front; the 4 stays at the end.

Example 3

head=list_node([]), pivot=7 → None

Constraints

The list has between 0 and 200 nodes
-100 ≤ node value ≤ 100
-200 ≤ pivot ≤ 200

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List Two Pointers

Similar problems

Drop the K-th Node From the Tail Medium Move the Tail to the Front Medium Sorted List, Unique Values Only Medium List Folded From Both Ends Medium Sorting a Linked List Medium

Input

head=list_node([6, 2, 9, 1, 5]), pivot=5

Expected

[2, 1, 6, 9, 5]

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.