Reverse Linked List II

Definition for Singly-Linked List

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

Solution

Iteration

TODO: explain image

Complexity

time: $O(n)$
space: $O(1)$

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    dummy = ListNode(next=head)
    p0 = dummy
    for _ in range(left-1):
        p0 = p0.next

    # reverse linked list btw `left` and `right`
    prev = p0
    curr = prev.next
    for _ in range(right-left+1):
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp
    
    # update 2 pointers, refer to image
    p0.next.next = curr
    p0.next = prev
    return dummy.next