Reverse Linked List II
Problem
head of a singly linked list and two 1-based positions
left ≤ right, reverse only the nodes from position left through
position right, leaving everything before and after untouched. Return the head
of the resulting list.head = [1,2,3,4,5], left = 2, right = 4Output[1,4,3,2,5]head = [5], left = 1, right = 1Output[5]1 ≤ n ≤ 500 · -500 ≤ Node.val ≤ 500 · 1 ≤ left ≤ right ≤ n · Follow-up: do it in one pass.
Try it yourself
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
}
}
left (a dummy covers
left = 1). Then repeatedly take the node after the segment's original first
node and move it to the front of the segment — after right - left moves
the segment is reversed.Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.
Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.
Open the Linked List Techniques guide →Approaches
Brute ForceCopy Values, Reverse the Sub-array
O(n)Space O(n)Copy all values into a list, reverse the slice
[left-1, right-1] with two pointers, then write the values back into
the nodes in order. Correct because only the order of values matters for the
output.
public ListNode reverseBetween(ListNode head, int left, int right) { List<Integer> vals = new ArrayList<>(); for (ListNode c = head; c != null; c = c.next) vals.add(c.val); for (int i = left - 1, j = right - 1; i < j; i++, j--) Collections.swap(vals, i, j); ListNode c = head; for (int v : vals) { c.val = v; c = c.next; } return head; }
Easy, but needs O(n) memory and rewrites values rather than relinking nodes.
BetterCut Out, Reverse, Reconnect
O(n)Space O(1)Locate before (node ahead of the segment), start and
end, remember after = end.next and cut the segment loose.
Reverse it with the standard three-pointer loop, then hook
before → end and start → after.
public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0, head), before = dummy; for (int i = 1; i < left; i++) before = before.next; ListNode start = before.next, end = start; for (int i = left; i < right; i++) end = end.next; ListNode after = end.next; end.next = null; // isolate the segment ListNode prev = null, cur = start; while (cur != null) { ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } before.next = end; // old end is the new segment head start.next = after; // old start is the new segment tail return dummy.next; }
Constant memory and reuses plain reversal, but walks the segment twice.
OptimalOne-Pass Front Insertion
O(n)Space O(1)Keep before fixed and let tail be the original first
node of the segment (it ends up last). Each step unlinks tail.next and
inserts it right after before. Every node in the range is visited
once.
public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0, head), before = dummy; for (int i = 1; i < left; i++) before = before.next; ListNode tail = before.next; // drifts to the end of the reversed segment for (int i = 0; i < right - left; i++) { ListNode move = tail.next; tail.next = move.next; // unlink move move.next = before.next; // put it at the segment front before.next = move; } return dummy.next; }
Dry run[1,2,3,4,5], left=2, right=4
- start1b2t3m45move 3 to front
- step 11b32t4m5move 4 to front
- step 21b432t5done ✔
Single pass, constant memory — answers the follow-up.
left = 1 work without a special case.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Copy Values, Reverse the Sub-array | O(n) | O(n) |
| Better | Cut Out, Reverse, Reconnect | O(n) | O(1) |
| Optimal | One-Pass Front Insertion | O(n) | O(1) |
- Off-by-one when walking to
before— positions are 1-based. - No dummy head — breaks when
left = 1because the head itself changes. - Forgetting to reconnect the segment's new tail to the rest of the list.
- Draw the list with
beforeandtaillabelled; show one insertion. - Explain that
tailnever moves — the nodes move around it. - Test
left = right,left = 1andright = n.