All problems

Reverse Rising Runs

Medium · linked list

You are given the head of a singly linked list. Cut the list into runs: a run is a stretch of consecutive nodes whose values are strictly increasing, and each run is made as long as possible. A new run starts whenever a node's value is less than or equal to the value before it.

Reverse the nodes inside every run, but keep the runs themselves in their original order. Return the head of the resulting list. For an empty list, return None.

For example, 1 → 3 → 5 → 2 → 4 → 4 splits into the runs [1, 3, 5], [2, 4] and [4]. The second 4 is equal to the one before it, so it starts a run of its own. Reversing each run gives 5 → 3 → 1 → 4 → 2 → 4.

The nodes you receive are ListNode objects with a val and a next.

Examples

Example 1

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

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

The runs are [1, 3, 5], [2, 4] and [4]. The last 4 equals its neighbour, so it begins a new run. Each run is reversed in place.

Example 2

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

Output: [2, 3, 2, 3]

The runs are [2], [2, 3] and [3], because each repeated value ends the previous run. Only [2, 3] changes.

Example 3

Input: head = [9, 6, 2]

Output: [9, 6, 2]

Every value is smaller than the one before it, so each node is a run of one and nothing moves.

Constraints