Nodes are instances of the provided ListNode class. Positions are counted from 1 at the head. Write reverse_stretch(head, left, right) that reverses the order of the nodes at positions left through right (inclusive), leaves every other node where it was, and returns the head of the resulting list.
Rearrange the original nodes by re-pointing next fields: don't create nodes and don't change any val.
In the examples, lists are written as Python lists, head first:
reverse_stretch([10, 20, 30, 40, 50, 60], 2, 5) # [10, 50, 40, 30, 20, 60]
reverse_stretch([10, 20, 30], 1, 3) # [30, 20, 10]
reverse_stretch([10, 20, 30], 1, 2) # [20, 10, 30]
reverse_stretch([10, 20, 30], 2, 2) # [10, 20, 30]
reverse_stretch([8], 1, 1) # [8]
Constraints: the list has n nodes with 1 <= n <= 200,000, and 1 <= left <= right <= n. Aim for a single O(n) pass with O(1) extra memory: the tests measure peak memory, so don't collect the nodes into a Python list, and don't recurse.
Show hint
Walk to the node just before position left (a placeholder node in front of the head saves a special case when left is 1). From there, reverse exactly right - left + 1 links, then stitch both ends of the reversed piece back to the rest of the list.