Reverse Linked List II

Share

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. Positions are 1-indexed.

Example 1
Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Output: [1, 4, 3, 2, 5]
Explanation: The sublist from position 2 to 4 ([2, 3, 4]) is reversed to [4, 3, 2].
Example 2
Input: head = [5], left = 1, right = 1
Output: [5]

Solution Approach

We use a single-pass approach. A dummy node is prepended to handle edge cases where reversal starts from the head. We advance to the node just before position left (called prev), then reverse the sublist in-place using an insertion technique.

  • Create a dummy node that points to head. Set prev = dummy.
  • Advance prev exactly left - 1 steps so it sits just before the sublist start.
  • Let curr = prev.next (the first node of the sublist to reverse).
  • Repeat right - left times: take the node after curr, remove it from its position, and insert it immediately after prev. This effectively reverses the sublist one node at a time.
  • Return dummy.next as the new head.
Java
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class ReverseLinkedListII {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        // Move prev to (left-1)-th node
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }

        ListNode curr = prev.next;

        // Perform (right - left) insertions
        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;
    }
}
Complexity Analysis:

Time complexity: O(n) where n is the length of the linked list. We traverse the list at most once.
Space complexity: O(1) since we reverse in-place using only a constant number of pointers.