TL;DR
Single-pass head insertion in front of an anchored predecessor — O(n) time, O(1) space.
Approach 1 — Brute force: copy values, reverse the slice
Read all values into an array, reverse the left..right slice, and write the values back over the nodes.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
vals: List[int] = []
node = head
while node:
vals.append(node.val)
node = node.next
vals[left - 1:right] = reversed(vals[left - 1:right])
node = head
for v in vals:
node.val = v
node = node.next
return head
Time O(n), space O(n). It passes for n <= 500, but it avoids the pointer manipulation the problem is meant to test, rewrites node values (often disallowed), and uses two passes where one is asked for.
Approach 2 — Cut, reverse, reconnect
Insight: the window is a smaller linked list. Walk to the boundaries, run the standard iterative reversal (repeatedly redirect curr.next to prev) across exactly right − left + 1 nodes, then repair the two seams: predecessor → new window head, and old window head (now the tail) → successor. A dummy node handles left = 1 without a special case.
The two seams to repair, for [1, 2, 3, 4, 5] with left = 2, right = 4:
flowchart LR
pre["1 (pre)"] -->|seam 1| h["4 (new head)"]
h --> n3["3"]
n3 --> tail["2 (tail)"]
tail -->|seam 2| after["5 (after window)"]
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
dummy = ListNode(0, head)
pre = dummy
for _ in range(left - 1):
pre = pre.next # node at position left-1
tail = pre.next # will end up last in the window
prev, curr = None, tail
for _ in range(right - left + 1):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
pre.next = prev # seam 1: before-window -> new head
tail.next = curr # seam 2: new tail -> after-window
return dummy.next
Walkthrough on [1, 2, 3, 4, 5], left = 2, right = 4: pre = 1, tail = 2. Reversing 3 nodes: 2→None, then 3→2, then 4→3→2; loop ends with prev = 4, curr = 5. Seams: 1.next = 4, 2.next = 5. Result [1, 4, 3, 2, 5].
Time O(n), space O(1). Conceptually two mini-passes over the window (walk + reverse), all within one left-to-right traversal of the list.
Approach 3 — One-pass head insertion (the classic follow-up answer)
Insight: anchor pre at position left−1 and keep start = the node that began at position left. Each iteration plucks the node just after start and re-inserts it directly after pre, at the front of the window. After one move the window 2→3→4 is 3→2→4; after two it is 4→3→2. Exactly right − left moves fully reverse the window, and the list stays valid after every step, so there is no separate repair step to forget.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
dummy = ListNode(0, head)
pre = dummy
for _ in range(left - 1):
pre = pre.next
start = pre.next
for _ in range(right - left):
moved = start.next # node to relocate to window front
start.next = moved.next # unlink it
moved.next = pre.next # it now points at current front
pre.next = moved # it becomes the new front
return dummy.next
Walkthrough on [1, 2, 3, 4, 5], left = 2, right = 4 (pre = 1, start = 2):
| move | relocated | list |
|---|
| 1 | 3 | 1→3→2→4→5 |
| 2 | 4 | 1→4→3→2→5 |
Two moves (right − left = 2) and done: [1, 4, 3, 2, 5]. Note start never moves — it just sinks to the window’s tail, which keeps start.next always pointing at the next node to pluck.
Time O(n) in a genuine single pass, space O(1).
Common pitfalls
left = 1: the returned head changes. Without a dummy node, this branch is where solutions break (see example [3, 7]).- In head insertion, linking
moved.next = start instead of moved.next = pre.next — correct on the first move, wrong on every later one.
- Off-by-one in loop counts: cut-and-reverse runs
right − left + 1 times (nodes), head insertion runs right − left times (moves). Mixing them up drops or over-rotates one node.
- Forgetting
tail.next = curr in Approach 2, orphaning the suffix after the window.
Pattern takeaway
Segment surgery on a linked list has two reliable idioms: (1) cut–reverse–reconnect, where you reuse the plain reversal and then fix exactly two seams, and (2) head insertion in front of a fixed anchor, which keeps the list valid after every step. Both lean on the same rule of thumb: park a pointer one node before the region you’ll modify, and use a dummy so that “one before the head” always exists.