92. Reverse Linked List II

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

Difficulty: Medium

$O(N)$ time, $O(1)$ space.

# 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]:
        if head is None:
            return head
        prev, cur = None, head
        # move pointers to "left"'s position
        while left > 1:
            prev = cur
            cur = cur.next
            left, right = left - 1, right - 1
        tail, con = cur, prev
        while right > 0:
            next = cur.next
            cur.next = prev  # reverse
            prev = cur
            cur = next
            right -= 1
        if con:
            con.next = prev
        else:
            # con could be None if prev was None and the second while loop never enters, this happens when left is 1
            # Example, [1, 2, 3, 4, 5], left = 1, right = 3, expected result is [3, 2, 1, 4, 5]
            # at this point, prev points to 3
            head = prev
        tail.next = cur

        return head