Reverse Linked List II

Medium#92reverse

You get a linked list and two positions, left and right, counted from 1. Reverse only the nodes from position left to position right, keep the rest as it is, and return the head. Our example: 3 → 8 → 1 → 6 → 4 → 2, left = 2, right = 5 — the answer is 3 → 4 → 6 → 1 → 8 → 2.

92 Reverse Linked List IIWalkthrough · 1×

Example: reverse positions 2..5 of 3 → 8 → 1 → 6 → 4 → 2: the part 8 → 1 → 6 → 4.

nonedummy381642
not touchedbefore, in front of the partcurnext, savedturned around

A dummy node in front of the head: there is always a node before the part, even when the part starts at the head

01/30
restart · back · play · step
Speed
1function reverseBetween(head, left, right):
2 dummy = new node whose next is head
3 before = dummy
4 repeat left - 1 times:
5 before = before.next
6 first = before.next
7 prev = none
8 cur = first
9 repeat right - left + 1 times:
10 next = cur.next
11 cur.next = prev
12 prev = cur
13 cur = next
14 before.next = prev
15 first.next = cur
16 return dummy.next
state
before
–
first
–
prev
–
cur
–
next
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. before stops on the node in front of the part, and the dummy guarantees there is one: with left = 1 before stays on the dummy, and dummy.next becomes the new head.
  2. Inside the part it is the card's reverse loop, run exactly right − left + 1 times; then cur stands on the first node after the part.
  3. Two links sew the part back: before → prev, its new first node, and first, now its last node, → cur. Every other link is untouched.

Complexity

Time O(n): before walks to the part, the loop walks through it, each node once at most. Memory O(1): a few pointers and one dummy node.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.