Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Reverse Linked List II

Problem (restated)

Given the head of a singly linked list and 1-based indices left and right (left ≤ right), reverse only the sublist between those positions and return the head.

Intuition

Walk a dummy to the node before left. Then, right - left times, take the node after cur and splice it to the front of the range (head-insertion). cur stays the original left node and marches toward the right as nodes jump in front of it.

Approaches

Dummy + range splice

Unverified

Time O(n)Space O(1)

Idea. dummy→head. Advance pre left-1 steps. Let cur = pre.next. For each remaining node in the range: nxt = cur.next; pull nxt out and insert it at pre.next.

Walkthrough. 1→2→3→4→5, left=2, right=4. pre is 1, cur is 2. First splice: 1→3→2→4→5. Second: 1→4→3→2→5.

Trade-offs. One pass, O(1) extra space. Dummy covers left = 1. If left == right the loop does nothing. LC 206 is this with the range equal to the whole list; LC 25 repeats it on every k-block.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number,
): ListNode | null {
  const dummy = new ListNode(0, head);
  let pre = dummy;
  for (let i = 0; i < left - 1; i++) pre = pre.next!;
  const cur = pre.next!;
  for (let i = 0; i < right - left; i++) {
    const nxt = cur.next!;
    cur.next = nxt.next;
    nxt.next = pre.next;
    pre.next = nxt;
  }
  return dummy.next;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number,
): ListNode | null {
  const dummy = new ListNode(0, head);
  let pre = dummy;
  for (let i = 0; i < left - 1; i++) pre = pre.next!;
  const cur = pre.next!;
  for (let i = 0; i < right - left; i++) {
    const nxt = cur.next!;
    cur.next = nxt.next;
    nxt.next = pre.next;
    pre.next = nxt;
  }
  return dummy.next;
}

Template connection

Reverse-range shape of Linked List Manipulation. Same prev / cur / nxt idea as whole-list reverse, but the insertion point pre is pinned at the start of the range.

Reflection

Walk to the node before left. Reverse [left, right], point the previous node at the new head, and point the range’s tail at the node after right.
left = 1 changes the head, which is why the dummy is there. left = right leaves the list unchanged.
If you lose the node after right, the tail of the list drops. Nodes outside the range stay put.