Reverse Linked List
Flip every pointer in a linked list using three references, and understand why the order of assignments matters
Problem Statement
Given the head of a singly linked list, reverse it and return the new head.
Input: 1 → 2 → 3 → 4 → 5 → null
Output: 5 → 4 → 3 → 2 → 1 → null
Input: 1 → 2 → null
Output: 2 → 1 → null
Input: null
Output: nullIntuition
You cannot reverse a linked list by moving values around cheaply — the point is to re-point the arrows. Node 1 currently points at 2; afterwards 2 must point at 1.
Here is the trap that makes this problem instructive:
The moment you flip a pointer, you lose the rest of the list
Set node1.next = None to start the reversal, and 2 → 3 → 4 → 5 is now unreachable. Nothing else refers to node 2. In a garbage-collected language it simply vanishes.
You must save the next node before overwriting the pointer.
The key insight
Walk the list carrying three references:
prev— the part already reversed (starts asnull, which becomes the new tail'snext)curr— the node being processednext— a temporary hold oncurr.next, saved before it is destroyed
Each step does exactly one thing: point curr backwards at prev, then shift all three references one position right.
Real-world analogy
Reversing a line of people who each have a hand on the shoulder of the person ahead. You cannot ask someone to turn around until you have noted who was in front of them — otherwise the rest of the line has no way back.
Watch it run
Approach
Initialise prev = null and curr = head
prev starts as null because the old head becomes the new tail, and a tail points to null.
While curr is not null, do four things in order
next = curr.next— save it before destroying itcurr.next = prev— flip the arrowprev = curr— the reversed portion growscurr = next— advance
The order is not negotiable. Any other sequence loses a reference.
Return prev
When the loop ends, curr is null and prev points at the last node processed — the new head.
Solution
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
self.val = val
self.next = next
def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
"""Reverse a singly linked list and return the new head."""
prev: Optional[ListNode] = None
curr = head
while curr:
next_node = curr.next # 1. save before overwriting
curr.next = prev # 2. flip the arrow
prev = curr # 3. reversed part grows
curr = next_node # 4. advance
return prev # curr is None; prev is the new headPython allows the four assignments as one tuple statement, which some find clearer:
def reverse_list_compact(head: Optional[ListNode]) -> Optional[ListNode]:
prev, curr = None, head
while curr:
curr.next, prev, curr = prev, curr, curr.next
return prevWhy the compact Python version works
curr.next, prev, curr = prev, curr, curr.next evaluates the entire right-hand side first, then assigns left to right. So curr.next on the right still refers to the original next node even though curr.next on the left is about to change. Writing the same thing as three separate statements in that order would be a bug.
The recursive version
def reverse_list_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
# Base case: empty list, or a single node which is already reversed.
if head is None or head.next is None:
return head
# Reverse everything after head; new_head is the final node of the list.
new_head = reverse_list_recursive(head.next)
# head.next is still the node just after head. Make it point back.
head.next.next = head
head.next = None
return new_headThe recursion reaches the end of the list first, then flips pointers on the way back up. head.next.next = head reads oddly but says something simple: the node after me should point at me. Setting head.next = null afterwards prevents a two-node cycle.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — each node is visited exactly once.
- Space — the iterative version uses three references. The recursive version uses
O(n)stack frames and will overflow on very long lists, which is why the iterative form is preferred in practice.
Edge Cases
Related Problems
- Middle of the Linked List — traversal with two pointers at different speeds
- Merge Two Sorted Lists — rewiring pointers to weave two lists together
- Linked List Cycle II — pointer manipulation where the list has no end