All problems

Partition List

Medium · linked list

You are given the head of a singly linked list and an integer 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 keep the order they had in the original list. Return the head of the rearranged list. An empty list stays empty. The nodes you receive are ListNode objects with a val and a next.

Examples

Example 1

Input: head = [5, 1, 4, 2, 6, 3], x = 4

Output: [1, 2, 3, 5, 4, 6]

1, 2 and 3 are below 4 and keep their order; 5, 4 and 6 are not below 4 and keep theirs.

Example 2

Input: head = [3, 1, 2], x = 10

Output: [3, 1, 2]

Every value is below 10, so nothing moves.

Example 3

Input: head = [2, 2], x = 2

Output: [2, 2]

Equal to x counts as the second group, so there is nothing to put in front.

Constraints