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.

reverse_linked_list_two.py

"""
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.
Follow up: Could you do it in one pass?

Example 1:
    Input: head = [1,2,3,4,5], left = 2, right = 4
    Output: [1,4,3,2,5]
Example 2:
    Input: head = [5], left = 1, right = 1
    Output: [5]

https://leetcode.com/problems/reverse-linked-list-ii/
"""


class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int):
        prev = None
        curr = head

        # # find where reversing begins
        for _ in range(left-1):  # the 1st node is at pos 1
            prev = curr
            curr = curr.next

        # we cannot use before_reverse.next when left is at 1, coz there is no before_reverse so we use start_reverse
        # store the last non reversed(not to be reversed) node
        start_reverse = curr
        # will be the tail of the last reversed list
        before_reverse = prev

        # # reverse a section
        for _ in range(left, right+1):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # # merge the reversed section (fix the reversed list position in the larger list)
        # the (left - 1) node to point to right
        if before_reverse and before_reverse.next:
            # before_reverse.next = last reversed node (prev)
            before_reverse.next = prev

        else:
            # if we started reversing from 1, then the last item reversed will be put at 1 (head)
            head = prev

        # the first reversed (left) node to point to the node at (right + 1)
        start_reverse.next = curr

        return head