Reverse Linked List II

Problem 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.

Examples

Constraints

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

Pointer Bookkeeping for Sub-reversal

To reverse a portion of the list in a single pass:

1. Locate the Boundaries: Move a pointer prev to the node immediately before the left position (index left - 1). The node at left becomes the tail of our reversed sub-segment.
2. Reverse the Sub-segment: We iterate right - left times. In each iteration, we pluck the node then (which is tail.next), move it to the position after prev, and adjust the adjacent links. For example, in 1 -> 2 -> 3 -> 4 -> 5 with left = 2, right = 4:

• prev = 1, tail = 2.
• First step (then = 3): 1 -> 3 -> 2 -> 4 -> 5.
• Second step (then = 4): 1 -> 4 -> 3 -> 2 -> 5. This reverses the sub-list in a single pass with O(1) extra memory.

Solution 1: Single Pass In-Place Reversal

Track boundaries using link pointers and shift sub-segment nodes step by step.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

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

        ListNode tail = prev.next; // first node of the sub-list to reverse

        // Reverse sub-list in place
        for (int i = 0; i < right - left; i++) {
            ListNode then = tail.next;
            tail.next = then.next;
            then.next = prev.next;
            prev.next = then;
        }

        return dummy.next;
    }
}

# 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:
            return None
            
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        
        # Move prev to position left - 1
        for _ in range(left - 1):
            prev = prev.next
            
        tail = prev.next  # first node of sub-list to reverse
        
        # Reverse sub-list
        for _ in range(right - left):
            then = tail.next
            tail.next = then.next
            then.next = prev.next
            prev.next = then
            
        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (!head) return nullptr;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;

        for (int i = 0; i < left - 1; i++) {
            prev = prev->next;
        }

        ListNode* tail = prev->next;

        for (int i = 0; i < right - left; i++) {
            ListNode* then = tail->next;
            tail->next = then->next;
            then->next = prev->next;
            prev->next = then;
        }

        return dummy->next;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we traverse the list nodes at most once.
• Space Complexity: O(1) auxiliary space as the reversal is performed in-place.

Where It Breaks

If the list is doubly-linked, the back pointers (prev) must be updated in tandem, otherwise the list structure is broken.

Common Mistakes

• Incorrect index offsets: Forgetting the dummy node wrapper. Without a dummy node, if left = 1, prev will be null, causing a null pointer dereference.
• Wrong link assignments: Swapping tail.next and then.next incorrectly, causing nodes to be dropped or creating infinite cycles.

Frequently Asked Questions

Why is a dummy node necessary here? If left = 1, the head of the list itself is reversed. A dummy node provides a stable parent link to the new head.

How does this behave if left == right? The inner loop right - left runs 0 times, so no nodes are modified, and the original list is returned as is.

← All Problems