Reverse Linked List II

MEDIUM✓ CHIP-TIMEDLC #92 — FULL STATEMENT ↗

The drill: Reverse only the run of nodes between two 1-indexed positions in a singly linked list, leaving everything before and after that window untouched, then hand back the original head.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A singly linked list arrives along with two 1-indexed positions, left and right, marking a contiguous window somewhere inside it.

The job is to reverse only the nodes inside that window, leaving every node before left and every node after right exactly as it was, wiring the reversed window back into the surrounding list seamlessly.

left and right always describe a valid window inside the list's bounds, and the original head is handed back — though if left is 1, the reversed window's front becomes the new head.

EX 01

head = [1, 2, 3, 4, 5] · left = 2 · right = 4

→ [1, 4, 3, 2, 5]

REVERSE AN INTERIOR WINDOW

EX 02

head = [1, 2, 3, 4, 5] · left = 1 · right = 5

→ [5, 4, 3, 2, 1]

REVERSE THE ENTIRE LIST

EX 03

head = [1] · left = 1 · right = 1

→ [1]

SINGLE NODE, NO-OP

list holds up to a few thousand nodes
left and right are 1-indexed and always within the list's bounds
left is always less than or equal to right
nodes outside the window keep their original order untouched

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Reversing the whole list is a known move; reversing a window in the middle just means the nodes outside the window need to keep pointing at whatever the window becomes.

HINT 2 THE STRUCTURE

Walk to the node just before the window and hold onto it — every node pulled out of the window can be spliced back in right after that anchor, one at a time, from the front of the window outward.

HINT 3 ONE STEP FROM THE ANSWER

Repeatedly detach the node right after the window's current front and re-insert it directly after the anchor. Do this (right − left) times and the window ends up fully reversed, still wired into the rest of the list.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE HEAD-INSERTION SPLICEPATTERN · HEAD-INSERTION SPLICEhead = [1, 2, 3, 4, 5] · left = 2 · right = 4

STEP 1

Reverse just the window from position 2 to position 4 in [1, 2, 3, 4, 5] — values 2, 3, 4 — using head-insertion splices. Nothing outside the window moves.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/reverse-linked-list-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        curr = prev.next
        for _ in range(right - left):
            nxt = curr.next
            curr.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt

        return dummy.next

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 15 LN

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        vals = []
        node = head
        while node:
            vals.append(node.val)
            node = node.next

        vals[left - 1:right] = vals[left - 1:right][::-1]

        node = head
        for v in vals:
            node.val = v
            node = node.next
        return head

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

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

        ListNode curr = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode nxt = curr.next;
            curr.next = nxt.next;
            nxt.next = prev.next;
            prev.next = nxt;
        }

        return dummy.next;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 17 LN

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) vals.add(n.val);

        int i = left - 1, j = right - 1;
        while (i < j) {
            int tmp = vals.get(i);
            vals.set(i, vals.get(j));
            vals.set(j, tmp);
            i++;
            j--;
        }

        ListNode node = head;
        for (int v : vals) {
            node.val = v;
            node = node.next;
        }
        return head;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED