92. Reverse Linked List II

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/reverse-linked-list-ii/
• topics: Linked List

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

Idea

dummy + 2 pointers + temp

# 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 not head or left == right:
            return head
 
        dummy = ListNode(0, head)
        prev = dummy
 
        for _ in range(left - 1):
            prev = prev.next
 
        cur = prev.next
        for _ in range(right - left):
            temp = cur.next
            cur.next = temp.next
            temp.next = prev.next
            prev.next = temp
 
        return dummy.next

Visual Example

Suppose the list is 1 -> 2 -> 3 -> 4 -> 5, and you want to reverse from left = 2 to right = 4.

1. Initial State:
   • prev points to 1, cur points to 2.
   • Sublist to reverse: 2 -> 3 -> 4.
2. First Iteration:
   • temp = cur.next = 3.
   • Update cur.next = temp.next → 2 -> 4.
   • Update temp.next = prev.next → 3 -> 2.
   • Update prev.next = temp → 1 -> 3 -> 2 -> 4 -> 5.
3. Second Iteration:
   • temp = cur.next = 4.
   • Update cur.next = temp.next → 2 -> 5.
   • Update temp.next = prev.next → 4 -> 3 -> 2.
   • Update prev.next = temp → 1 -> 4 -> 3 -> 2 -> 5.