LeetCode 92. Reverse Linked List II

Problem Statement

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes from position left to position right and return the modified list.

Solution Strategy

A stack provides an elegant mechanism to reverse elements in-place without complex pointer manipulation. The stack naturally reverses the order of nodes as we pop them.

Consider the input head = [1,2,3,4,5], left = 2, right = 4. The list naturally divides into three segments:

• Prefix: nodes before position left (node 1)
• Reversible section: nodes from left to right (nodes 2, 3, 4)
• Suffix: nodes after position right (node 5)

A dummy node (value -510) placed before the reversible section simplifies boundary handling significantly.

Step-by-step visualization:

When pushing nodes at positions 2, 3, and 4 onto the stack, we get:

• Stack contents after traversal: [2, 3, 4]

During popping:

1. Pop 4, connect to dummy → dummy → 4
2. Pop 3, connect 4 → 3 → dummy → 4 → 3
3. Pop 2, connect 3 → 2 → dummy → 4 → 3 → 2

Finally, connect the last popped node to the suffix node (5) and attach the prefix to the start of the reversed section.

Implementation (Java)

public ListNode reverseBetween(ListNode head, int left, int right) {
    int position = 1;
    Deque<ListNode> stack = new ArrayDeque<>();
    
    ListNode sentinel = new ListNode(0);
    ListNode beforeStart = null;
    ListNode afterEnd = null;
    ListNode current = head;
    
    while (current != null) {
        if (position == left - 1) {
            beforeStart = current;
        } else if (position >= left && position <= right) {
            stack.push(current);
        } else if (position == right + 1) {
            afterEnd = current;
        }
        current = current.next;
        position++;
    }
    
    ListNode traversalPtr = sentinel;
    while (!stack.isEmpty()) {
        traversalPtr.next = stack.pop();
        traversalPtr = traversalPtr.next;
    }
    
    traversalPtr.next = afterEnd;
    
    if (beforeStart == null) {
        return sentinel.next;
    }
    
    beforeStart.next = sentinel.next;
    return head;
}

LeetCode 25. Reverse Nodes in k-Group

Problem Statement

Given the head of a linked list and an integer k, reverse every k consecutive nodes. If the total number of nodes is not divisible by k, leave the remaining nodes unchanged. The reversal must involve actual node swapping, not just value modification.

Solution Strategy

This problem extends the partial reversal concept by applying it iteratively to each group of k nodes.

For input head = [1,2,3,4,5], k = 2:

1. Traverse the list, pushing nodes onto the stack
2. When the stack reaches size k, pop all elements and connect them
3. For the final group (node 5 alone), since its stack size is less than k, it remains unchanged

Key insight: After processing all complete groups, if any nodes remain in the stack, they form an incomplete group that should preserve their original order. The firstElement() method retrieves the bottom of the stack (the first element pushed), which serves as the head of the remaining segment.

Implementation (Java)

public ListNode reverseKGroup(ListNode head, int k) {
    Deque<ListNode> nodeStack = new ArrayDeque<>();
    ListNode dummy = new ListNode(-1);
    ListNode resultPtr = dummy;
    ListNode traversal = head;
    
    while (traversal != null) {
        nodeStack.push(traversal);
        traversal = traversal.next;
        
        if (nodeStack.size() == k) {
            while (!nodeStack.isEmpty()) {
                resultPtr.next = nodeStack.pop();
                resultPtr = resultPtr.next;
            }
        }
    }
    
    if (!nodeStack.isEmpty()) {
        resultPtr.next = nodeStack.peekFirst();
    } else {
        resultPtr.next = null;
    }
    
    return dummy.next;
}

Complexity Analysis

Both solutions achieve O(n) time complexity with a single traversal. Space complexity is O(k) for Problem 25 (maximum stack size equals k), and O(right - left + 1) for Problem 92.