noodleProblems/
Reverse Linked List II
#98

Reverse Linked List II

AlgorithmmediumLinked List

Given the head of a singly linked list and two 1-based positions left <= right, reverse the nodes from position left to position right inclusive, and return the head of the modified list. Nodes outside that range keep their order.

Lists are shown in array notation for readability — reverseBetween([1,2,3,4,5], 2, 4) reverses the middle three to give [1,4,3,2,5].

Example cases

  • middle reversed
    in head = [1,2,3,4,5]12345nullleft = 2right = 4
    out [1,4,3,2,5]14325null
    Positions 2..4 (2,3,4) reverse to 4,3,2.
  • single node
    in head = [5]5nullleft = 1right = 1
    out [5]5null
    A one-node range is unchanged.
  • whole list
    in head = [1,2,3,4,5]12345nullleft = 1right = 5
    out [5,4,3,2,1]54321null

Constraints

  • The number of nodes in the list is in the range [1, 500].
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n
Saved
head =
[1,2,3,4,5]
left =
2
right =
4