LeetCode 92: Reverse Linked List II

link

One pass

We jump to the left node and reverse (right-left+1) number of nodes. We then fix two pointers:

  1. prev -> reversed_head
  2. reversed_tail -> next

To simplify the (prev, curr) logic we introduce a dummy node.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverse(self, head, reverse_count):
        prev, curr = None, head
        while reverse_count > 0:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

            reverse_count -= 1
        
        return prev, curr

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        
        jump_count = left-1
        prev, curr = dummy, head
        while jump_count > 0:
            prev = curr
            curr = curr.next
            jump_count -= 1
        reverse_count = right-left+1
        reversed_head, next_head = self.reverse(curr, reverse_count)

        curr.next = next_head
        prev.next = reversed_head
        
        return dummy.next

Leave a comment