The problem
Given the head of a singly linked list, reverse the list and return the new head.
Input: 1 → 2 → 3 → 4 Output: 4 → 3 → 2 → 1
Picture it
A linked list is like a train: each coach holds a value and a coupling to the next coach. The only way in is the first coach (the head). To reverse it, we walk along with three markers: prev (the part already reversed), curr (the coach we’re fixing) and nxt (the rest of the train, remembered so we don’t lose it). For each coach we flip its coupling to point backwards.
How to recognise it
- The input is a singly linked list: each node knows only the next node, so you cannot step backwards.
- You must change the direction of the links, not just read values in reverse.
- The answer is a new head, which was the old tail.
- The follow-up asks for O(1) extra space: no array of nodes and no recursion stack.
- Reversing a list (or part of one) is a building block for harder problems such as Reorder List and Reverse Nodes in k-Group, so it is worth knowing by heart.
Start with brute force
Walk the list once and store every node in a Python list. Then use the indices, which can go backwards, to point each node at the one before it.
def reverse_brute(head):
nodes = []
while head:
nodes.append(head)
head = head.next
if not nodes:
return None
for i in range(len(nodes) - 1, 0, -1):
nodes[i].next = nodes[i - 1]
nodes[0].next = None
return nodes[-1]
Time is O(n) and extra space is O(n). With LeetCode's limit of 5,000 nodes this is not too slow; the problem is memory. It stores a reference to every node only because a singly linked list cannot be walked backwards, and the follow-up asks you to avoid exactly that.
From brute force to the idea
- Find the waste. The array exists only so that each node can reach "the node before me". But while you walk forwards, the node before is the one you just left. You only ever need that one.
- Keep three references.
previs the head of the part already reversed (it starts asNone),curris the node being fixed, andnxtremembers the rest of the list. - Save before you cut.
nxt = curr.nextmust come first. Oncecurr.nextpoints backwards, the rest of the list is unreachable unless you saved it. - Flip one link.
curr.next = prevturns the arrow around. The very first node getsNone, so it becomes the new tail. - Move both forward.
prev = currandcurr = nxt. Whencurrfalls off the end,previs the old tail, now the head.
This is the key idea: save the next node, point the current node back, then move both pointers one step forward.
The key idea
Remember next, point curr back at prev, then move both forward. O(n) time, O(1) extra space.
Python solution
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prevIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n): one pass to collect, one to relink | O(n): a reference to every node |
| Three pointers (shown code) | O(n): each node is visited once and its link changed once | O(1): only prev, curr and nxt |
Edge cases
- Empty list (
headisNone): the loop never runs and the code returnsNone. - One node: its
nextis set toNone(it already was) and it is returned. - Two nodes (
1 → 2): returns2 → 1, and node 1'snextis nowNone, so there is no cycle. - Long list: the loop is iterative, so 5,000 or even 10^6 nodes are fine. A recursive version would raise
RecursionErrorat around 1,000 nodes, Python's default recursion limit. - Old head reference: after the call, the caller's old
headvariable points to the new tail, a list of one node. Always use the returned head.
Common mistakes
- Writing
curr.next = prevbefore savingcurr.next, which loses the rest of the list after one step. - Returning
currinstead ofprev. At the endcurrisNone. - Forgetting that the old head must end with
None. StartingprevatNonehandles this; starting it atheadcreates a cycle. - Swapping values instead of links. It gives the right printout but is not what the problem asks, and it needs O(n) space or O(n²) time to reach the back.
Given the head and two positions left ≤ right (1-based), reverse only the nodes from position left to right and return the head. For 1 → 2 → 3 → 4 → 5 with left 2 and right 4 the answer is 1 → 4 → 3 → 2 → 5. Describe your approach, then write it if you like.
Compare with our answer
Walk to the node just before the section, using a dummy node in case the section starts at the head. Reverse exactly right − left + 1 nodes with the same three-pointer loop. Afterwards prev is the section's new first node and curr is the first node after it; the old first node of the section is now its last, so link it to curr.
def reverse_between(head, left, right):
dummy = Node(0, head)
before = dummy
for _ in range(left - 1):
before = before.next
prev, curr = None, before.next
for _ in range(right - left + 1):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
tail = before.next # first node of the section, now its last
tail.next = curr
before.next = prev
return dummy.next
Time O(n), space O(1).
A strong answer mentions: a dummy node so left = 1 needs no special case, counting the nodes to reverse instead of running to the end, and reconnecting both ends of the reversed section.
1. A list of 10^6 nodes must be reversed in place, using O(1) extra memory. Which approach fits best?
Three pointers use constant memory and one pass. Recursion needs one stack frame per node (and fails in Python long before 10^6), the array is O(n) memory, and reaching the "last" node again each time costs O(n) per swap.
2. Why does the shown code use O(1) extra space for a list of any length?
The same three variables are reused on every step and no new nodes are created; the existing nodes are relinked. Nothing is freed, and the loop visits every node, not half of them.
3. A learner drops nxt = curr.next and writes curr = curr.next as the last line of the loop. What does it return for 1 → 2 → 3?
After curr.next = prev, curr.next is None, so curr = curr.next ends the loop after the first node, and prev (node 1, with no next) is returned. Nodes 2 and 3 are unreachable.
Score 60% or more and the lesson is marked complete.