Reverse Linked List II
MediumLinked List · Cisco
You are given the head of a singly linked list and two integers left and right with left <= right. Positions are 1-indexed: the head is position 1.
Reverse the order of the nodes from position left to position right (inclusive), leaving every node before and after that segment where it is. Return the head of the resulting list, which is a new node if left = 1.
Rearrange the nodes themselves (relink next pointers) rather than copying values into a new list. In the examples, lists are written as arrays from head to tail.
Example 1
- Input:
- head = [10, 20, 30, 40, 50, 60], left = 3, right = 5
- Output:
- [10, 20, 50, 40, 30, 60]
- Explanation
- Positions 3 to 5 hold
30, 40, 50. Reversing just that part gives50, 40, 30, while10, 20before it and60after it stay in place.
Example 2
- Input:
- head = [4, 8], left = 1, right = 2
- Output:
- [8, 4]
- Explanation
- The segment is the whole list, so the new head is the old tail, 8.
Example 3
- Input:
- head = [-1, 0, 7], left = 2, right = 2
- Output:
- [-1, 0, 7]
- Explanation
- A segment of length one is unchanged by reversal.
Constraints
- The number of nodes
nis in the range[1, 500] -500 <= Node.val <= 5001 <= left <= right <= n