Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Class Node:
    data (int)
    next (Node)

Input Format

First Parameter - Node head

Second Parameter - number left

Third Parameter - number right

Output Format

Return the head of list.

Example 1:

Input : 
    head = 1 2 3 4 5  
    left = 2 
    right = 4
Output : 
    1 4 3 2 5
Explanation : 
Nodes within indices [2,4] are 2 3 4 , Hence they need to be reversed. Thus output is 1 4 3 2 5 where 4 3 2 are reverse of 2 3 4.

Example 2:

Input :
    head = 5 
    left = 1
    right = 1
Output : 
    5
Explanation : 
Node within indices [1,1] are 5. Hence output is 5.

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.data <= 500
• 1 <= left <= right <= n
• Expected Time Complexity: O(N).
• Expected Auxiliary Space: O(1).