#92 Reverse Linked List II

frequently reported atAmazon Microsoft Meta

the problem

In plain words

Given the head of a singly linked list and two positions left ≤ right (counted from 1), reverse only the nodes from position left to position right, and return the head of the list.

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

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

in head = [5], left = 1, right = 1

out [5]

1 ≤ n ≤ 500
-500 ≤ Node.val ≤ 500
1 ≤ left ≤ right ≤ n
Follow-up: one pass

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Stand on the node just before the section (a dummy covers left = 1). The section's first node will end up as its last. So keep lifting the node right after it and inserting it at the front of the section — right − left lifts, one pass.

solutions

From brute force to optimal

Put the nodes in an ArrayList, reverse the sub-range, then rewrite every next in the new order.

Collect the nodes.
Collections.reverse(nodes.subList(left − 1, right)).
Relink nodes[i].next = nodes[i + 1]; the last gets null.

timeO(n)

One pass to collect, one to relink.

spaceO(n)

The array of node references.

javajava.util.*

1class Solution {2    public ListNode reverseBetween(ListNode head, int left, int right) {3        List<ListNode> nodes = new ArrayList<>();4        for (ListNode p = head; p != null; p = p.next) nodes.add(p);5        Collections.reverse(nodes.subList(left - 1, right)); // positions are 1-based6        for (int i = 0; i + 1 < nodes.size(); i++) nodes.get(i).next = nodes.get(i + 1); // relink in the new order7        nodes.get(nodes.size() - 1).next = null;8        return nodes.get(0);9    }10}

before = the node before position left; first = the section's first node. Repeat right − left times: lift first.next and insert it right after before.

dummy → head; walk before left − 1 steps from dummy.
first = before.next.
Repeat right − left times: move = first.next; first.next = move.next; move.next = before.next; before.next = move.
Return dummy.next.

timeO(n)

At most one walk to left, then a constant amount of work per moved node.

spaceO(1)

Four references and a dummy.

javajava.util.*

1class Solution {2    public ListNode reverseBetween(ListNode head, int left, int right) {3        ListNode dummy = new ListNode(0, head);    // left may be 1: the head itself moves4        ListNode before = dummy;5        for (int i = 1; i < left; i++) before = before.next; // node just before position left6        ListNode first = before.next;              // ends up as the LAST node of the reversed part7        for (int i = 0; i < right - left; i++) {8            ListNode move = first.next;            // the node right after `first`...9            first.next = move.next;                // ...is lifted out...10            move.next = before.next;               // ...and inserted at the front of the section11            before.next = move;12        }13        return dummy.next;14    }15}

in the room

How to say it in the interview

talk track

Clarify 1-based positions, and that left can be 1 — so the head can change: dummy node.
Name the roles: before stays put, first stays the same node but slides back, move is the node being lifted.
Dry-run [1,2,3,4,5], 2..4 out loud: 1→3→2→4→5, then 1→4→3→2→5.

traps

Walking left steps instead of left − 1 from the dummy — before must stop just before the section.
No dummy: with left = 1 the head changes, and returning the old head loses the reversed part.

what they ask next

Follow-ups

Without the front-insertion trick?

Cut the section out, reverse it with prev/curr/next (LC 206), then reconnect: before.next = new section head, old section head.next = the node after the section.

Reverse every block of k nodes?

That's LC 25 (below): the same section reversal, repeated block by block, leaving a short last block alone.

before you submit

Edge cases to test

left = right → nothing changes.
left = 1 → the head changes.
right = n → the old tail becomes the section's first node.
A one-node list.

practise next