7.7 Reverse Linked List II

7.7.1 Problem Metadata

7.7.2 Description

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.

7.7.3 Examples

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Input: head = [5], left = 1, right = 1
Output: [5]

7.7.4 Constraints

  • The number of nodes in the list is n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

7.7.5 Solution - Head Insertion

7.7.5.1 Walkthrough

This solution uses a head insertion technique to reverse the sublist in-place with a single pass.

Core Strategy:

  1. Find prev, the node before position left
  2. Keep curr fixed at position left (it becomes the tail of reversed portion)
  3. Repeatedly take curr.next and insert it at position left (right after prev)

Key Insight: Instead of standard reversal, we “bubble” each node to the front of the reversal range. After each iteration, curr.next moves one position to the right.

Example: Reverse positions 2-4 in [1,2,3,4,5]:

Initial: 1 → 2 → 3 → 4 → 5
         prev curr

Step 1: Move 3 to front of range
        1 → 3 → 2 → 4 → 5
        prev     curr

Step 2: Move 4 to front of range
        1 → 4 → 3 → 2 → 5
        prev         curr

Result: [1,4,3,2,5]

7.7.5.2 Analysis

  • Time Complexity: O(n) - Single pass to position left, then right - left operations
  • Space Complexity: O(1) - Only pointer variables used

7.7.5.3 Implementation Steps

  1. Create dummy node, find prev (node before position left).
  2. Set curr to prev.next (the node at position left).
  3. For right - left iterations:
    • Save next = curr.next
    • Remove next from its position: curr.next = next.next
    • Insert next after prev: next.next = prev.next; prev.next = next
  4. Return dummy.next.

7.7.5.4 Code - Java

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || left == right) {
        return head;
    }

    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    for (int i = 1; i < left; i++) {
        prev = prev.next;
    }

    ListNode curr = prev.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = curr.next;
        curr.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }

    return dummy.next;
}