Reverse Linked List II

Head insertion behind a fixed anchor, one pass

time O(n)space O(1)

Reversing a middle segment is awkward with the usual three-pointer reversal because four boundary pointers have to be stitched back together at the end. Head insertion avoids the stitching entirely. Fix one anchor, pre, on the node just before the window and keep start on the window's first node. Each step plucks the node after start and re-inserts it directly after pre. The plucked node lands in front of everything reversed so far, and start is pushed one slot to the right without being moved explicitly. After n - m such moves the window is reversed and both boundaries were maintained the whole time. The dummy node means the anchor exists even when the window begins at the head.

Details

Animated on: list = [1, 2, 3, 4, 5], m = 2, n = 4. Reverse the nodes from position m to n (1-indexed) in one pass. Answer: [1, 4, 3, 2, 5].

Problem:Reverse Linked List IIMedium

Pattern:Linked List Manipulation

Head insertion behind a fixed anchor, one pass

step 1 / 8

[0]

[1]

[2]

[3]

[4]

Reverse only positions 2..4 (1-indexed), the tinted window, in one pass. A dummy node sits before the head so the node BEFORE the window always exists — even when m = 1 and the window starts at the head.

Pseudocode

1FUNCTION reverseBetween(head, m, n)
2  dummy.next <- head
3  pre <- dummy
4  FOR i <- 1 TO m - 1
5    pre <- pre.next
6  start <- pre.next
7  FOR i <- 1 TO n - m
8    then <- start.next
9    start.next <- then.next
10    then.next <- pre.next
11    pre.next <- then
12  RETURN dummy.next

← / → step · space play · Home restart

Every step in words

Show all 8 steps

Reverse only positions 2..4 (1-indexed), the tinted window, in one pass. A dummy node sits before the head so the node BEFORE the window always exists — even when m = 1 and the window starts at the head.
Walk pre forward 1 step(s) from the dummy: it stops on value 1, the last node OUTSIDE the window. pre never moves again — it is the fixed anchor every plucked node gets re-inserted behind.
start <- pre.next = 2, the first node of the window. start also never moves in the pointer sense: it keeps sliding right as nodes are inserted in front of it, and ends up LAST in the window. 2 node(s) will be moved.
Move 1 of 2: then <- start.next = 3. This is the node to pluck out and drop directly after pre, in front of everything already reversed.
Three relinks: start.next skips over 3, 3.next takes the old window head 2, and pre.next <- 3. The window now reads [3, 2, 4] — start (2) drifted one slot right without anyone touching it.
Move 2 of 2: then <- start.next = 4. This is the node to pluck out and drop directly after pre, in front of everything already reversed.
Three relinks: start.next skips over 4, 4.next takes the old window head 3, and pre.next <- 4. The window now reads [4, 3, 2] — start (2) drifted one slot right without anyone touching it.
After 2 move(s) the window is reversed in place: [1, 4, 3, 2, 5]. Nothing outside the window was touched, every node was visited once, and dummy.next is still the true head — which is why the dummy exists.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Reverse Linked List II in the editor All Linked List problems Back to roadmap