PYTHON & CODING · QUESTION 23
How would you reverse a singly linked list?
On this page
Iterate through the list while keeping three references: the previous node, the current node, and the next node. Save the next node before changing the current node’s link, point the current node backward, then advance both references. When traversal ends, the previous node is the new head. The iterative solution takes O(n) time and O(1) extra space.
LET'S MAKE IT SIMPLE
First, the idea in plain English
Each node in a singly linked list points only forward. To reverse it, visit each node and redirect its link toward the node that came before it. Because changing a link could lose the rest of the list, first save the next node. Keep doing this until there are no nodes left; the last node visited becomes the new first node.
A USEFUL COMPARISON
Picture it this way
Imagine a line of people holding the shoulder of the person ahead. To reverse the line safely, each person must remember who was ahead before turning to hold the previous person. If they let go without remembering, the rest of the line is lost. In code, the saved next reference preserves the unprocessed nodes.
FOLLOW THE JOURNEY
Reverse each link while preserving the unvisited list
Track previous, current, and next references through one iteration.
The next pointer must be saved before current.next is changed. Otherwise the not-yet-reversed remainder becomes unreachable.
A linked list’s arrows are reversed one node at a time using previous, current, and next references until previous points to the new head.
How to read this visual
The next pointer must be saved before current.next is changed. Otherwise the not-yet-reversed remainder becomes unreachable.
UNDER THE HOOD
How it works, step by step
Initialize references
Set previous to None and current to the original head.
Why it matters: The first node will point to nothing after reversal.
Save the remainder
Before changing a link, store current.next in next_node.
Why it matters: This preserves access to nodes that are still unprocessed.
Reverse one link
Set current.next to previous, then advance previous and current.
Why it matters: Each iteration adds one node to the reversed prefix.
Return the new head
When current is None, return previous.
Why it matters: The original tail is now the first node.
OUTSIDE THE TEXTBOOK
A practical example
For A → B → C, start with previous = None and current = A. Save B, point A to None, then process B and point it to A. Finally process C and point it to B. Traversal ends and C is the new head: C → B → A.
GO A LITTLE DEEPER
Technical details that matter
- The invariant is that previous heads a correctly reversed prefix and current heads the untouched remainder.
- An empty list returns None; a one-node list returns the same node without special-case mutation.
- An iterative version avoids recursion depth proportional to list length.
- If nodes are shared elsewhere or the structure is immutable, changing links in place may be inappropriate; create new nodes or preserve ownership instead.
def reverse_list(head):
previous = None
current = head
while current is not None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previousThe loop processes every node once. Saving next_node before changing current.next keeps the remaining list reachable; previous becomes the new head after the loop.
MAKE A GOOD CHOICE
When is this useful?
- Reversing a singly linked list in place when node ownership allows mutation.
- Demonstrating pointer invariants and careful state updates.
- Understanding iterative alternatives to recursive list processing.
A recursive solution can be concise for small lists but uses O(n) call-stack space and may hit recursion limits. If mutation is not allowed, build a new list instead.
WATCH OUT FOR
Common misunderstandings
- Overwriting current.next before saving the rest of the list.
- Returning the original head instead of the new head.
- Forgetting that an empty list is a valid input.
REAL-WORLD TRADE-OFFS
Limitations and failure cases
- The in-place algorithm mutates the original structure.
- The function assumes an acyclic list; a cycle would prevent termination.
- The untyped example assumes nodes expose a mutable next attribute.
WHAT TO REMEMBER
Key takeaways
- 1Use previous, current, and next references.
- 2Save the next node before reversing the current link.
- 3Return previous after traversal ends.
- 4The iterative solution is O(n) time and O(1) extra space.
PRACTICE THE FOLLOW-UP
What might an interviewer ask next?
Why do you need three references?
Previous is the reversed prefix, current is the node being changed, and next preserves access to the unprocessed remainder.
What are the complexities?
Every node is visited once, so time is O(n). The iterative version uses a fixed number of references, so extra space is O(1).
How would you detect a cycle first?
Floyd’s tortoise-and-hare algorithm advances two references at different speeds; if they meet, a cycle exists. Reversal itself assumes a finite acyclic list.
SAY IT OUT LOUD
How to explain this in an interview
“I would walk through the list with previous, current, and next references. Before changing current’s link, I save its next node so the remaining list stays reachable. Then I point current backward and advance. When current becomes empty, previous is the new head. Each node is processed once, giving O(n) time and O(1) extra space.”
Connect this question to the roadmap topic it supports.