Leetcode 92 -- Reverse Linked List II.py

# Leetcode 92: Reverse Linked List II
# https://leetcode.com/problems/reverse-linked-list-ii/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy

        for i in range(left - 1):
            prev = prev.next

        curr = prev.next
        # want to reverse 2-4
        # 1 -> 2 -> 3 -> 4 -> 5
        # prev = 1
        # curr = 2
        # walk thru one switch in the loop
        # dummy node temp set to 3
        # 2 -> 4
        # 4 -> 2
        # prev -> 3
        for i in range(right - left):
            temp = curr.next # temp = 3
            curr.next = temp.next # curr -> 4
            temp.next = prev.next # temp -> 2
            prev.next = temp # pre -> 3

        return dummy.next

#time complexity: O(N)
#space complexity: O(1)