Problem Statement

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

Examples

Solution

Points of Interest

This is a modified version of Linked list in-place reversal problem.

1. We have three parts of linked list we need to look at
   1. Part before the range to be flipped
   2. Range itself
   3. Part after the range to be flipped
2. Note that 1st and 3rd parts are not to be reversed and kept as it is, while 2nd part should be reversed
3. Moreover, if start of range is not head, the result will send the original head, with linkages changes accordingly.
4. While, if start is head itself, the result will be the enb of the range, with linkages changes accordingly.

Algo

1. Initialize cur and prev variables with head and None
2. Decrease left integer by one. This signifies that we have visited head and countdown to read starting of the range has started
3. Start a loop which executes till either left is 0 or cur is None
   1. Inside move prev and cur forward
   2. Also decrease both left and right by 1
4. Keep a note of ListNode just before starting of the range and ListNode representing start of the range in range_prev and range_start respectively. These will be prev and cur respectively.
5. Reset prev to None
6. Start a loop which executes till either right is 0 or cur is None. Note that we are using cur from last loop.
   1. Internally, set next of cur to prev, and move prev and cur forward.
   2. Also decreased right by 1
7. Is range_prev is not None, set next of range_prev to prev
8. Set next of next of range_start to cur
9. If start of the range was head, then return prev
10. Else, return the original head

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    is_left_one = (left == 1)
    
    cur = head
    prev = None
    left -= 1
    while left and cur:
        prev = cur
        cur = cur.next
        left -= 1
        right -= 1
    
    range_prev, range_start = prev, cur

    prev = None
    while right and cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
        right -= 1
    
    if range_prev:
        range_prev.next = prev
    range_start.next = cur

    if is_left_one:
        return prev
    else:
        return head

Complexity

$\textbf{Time Complexity} = O(N)$

• Even though we have 2 loops, we are visiting each ListNode at most 1 time

$\textbf{Space Complexity} = O(1)$

• We are using few constant size variables, that are reused in loops