Reverse linked List II

92.Reverse Linked List II

Linked List

Problem Statement:

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.

Example:

Input:

head = [1→2→3→4→5]
left = 2, right = 4

→

Output:

[1→4→3→2→5]

Nodes from position 2 to 4 are reversed.

Algorithm:

1. Use dummy node to handle edge cases (e.g., when left = 1)
2. Move prev pointer to node just before reversal starts
3. Key concept: "Bubbling" nodes down:
   • prev and curr stay fixed
   • Continuously move next node to front of reversed section
   • Current "bubbles" down as nodes are moved in front
4. Repeat moving nodes (right - left) times

Complexity:

Time: O(n) | Space: O(1)

Java Solution:

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || left == right) return head;
    
    // Dummy node to handle edge cases
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;
    
    // Move to node before reversal starts
    for (int i = 0; i < left - 1; ++i) 
        prev = prev.next;
    
    ListNode curr = prev.next, next = null;

    // Remember - prev and curr stay constant, curr just "bubbles" down
    for (int i = 0; i < right - left; i++) {
        next = curr.next;           // Save next node
        curr.next = next.next;      // Skip over next

        next.next = prev.next;      // Move next to front
        prev.next = next;           // Point prev to next
    }
    
    return dummy.next;
}

Python Solution:

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    if not head or left == right:
        return head
        
    # Setup dummy node
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    
    # Move to node before reversal
    for _ in range(left - 1):
        prev = prev.next
        
    curr = prev.next
    
    # Bubble nodes down
    for _ in range(right - left):
        next_node = curr.next
        curr.next = next_node.next
        
        next_node.next = prev.next
        prev.next = next_node
        
    return dummy.next

C++ Solution:

ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (!head || left == right) return head;
    
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prev = dummy;
    
    for (int i = 0; i < left - 1; ++i)
        prev = prev->next;
        
    ListNode* curr = prev->next;
    ListNode* next;
    
    for (int i = 0; i < right - left; i++) {
        next = curr->next;
        curr->next = next->next;
        
        next->next = prev->next;
        prev->next = next;
    }
    
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}