All problems

Reverse Linked List II

Medium · linked list

You are given the head of a singly linked list and two positions left and right, counted from 1 at the head. Reverse the part of the list that runs from position left to position right, both included. Every node before left and after right stays exactly where it is.

Return the head of the resulting list. If left equals right, nothing changes.

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

Examples

Example 1

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

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

Positions 2 to 4 hold 2, 3, 4. They come back as 4, 3, 2, between the untouched 1 and 5.

Example 2

Input: head = [3, 5], left = 1, right = 2

Output: [5, 3]

The part to reverse starts at the head, so the head changes.

Example 3

Input: head = [7, 8, 9], left = 2, right = 2

Output: [7, 8, 9]

Constraints