86. Reverse Linked List II

Anchor a pointer just before position left. Then repeatedly take the node after the current one and splice it to the front of the sublist (right after the anchor). After right-left such moves, the sublist is reversed in place.

Idea

Reverse only the segment [left, right] without touching the rest. A dummy node before the head handles the case left == 1 cleanly. Walk prev to the node just before position left; the node at left becomes the tail of the reversed segment (cur). Then, right - left times, unlink cur.next and insert it right after prev — head-insertion — which reverses the segment.

Algorithm

1. dummy -> head; move prev forward left - 1 steps. cur = prev.next.
2. Repeat right - left times:
   • nxt = cur.next.
   • cur.next = nxt.next (skip nxt).
   • nxt.next = prev.next (nxt points to current segment head).
   • prev.next = nxt (nxt becomes new segment head).
3. Return dummy.next.

Worked example: list 1→2→3→4→5, left = 2, right = 4

• prev at 1, cur at 2. Move 3 to front → 1→3→2→4→5. Move 4 to front → 1→4→3→2→5.

Result: 1→4→3→2→5.

Complexity

• Time: O(n) — a single pass.
• Space: O(1).

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        ListNode cur = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode nxt = cur.next;
            cur.next = nxt.next;
            nxt.next = prev.next;
            prev.next = nxt;
        }
        return dummy.next;
    }
}