Loading learning content...
If there's one operation that epitomizes linked list mastery, it's reversal. The ability to reverse a linked list—transforming A → B → C → D into D → C → B → A—is not merely a coding exercise. It's a litmus test for your understanding of pointer manipulation, a building block for dozens of other algorithms, and one of the most frequently asked interview questions across the industry.
But reversing a linked list is subtle. Unlike arrays where you can simply swap elements from opposite ends, linked lists don't give you random access. You can't "look back" without first storing a reference. You must carefully orchestrate pointer reassignments, or risk losing your chain entirely—nodes floating in memory, unreachable and lost.
This page will take you from intuition to mastery. You'll understand why reversal works the way it does, see multiple implementation strategies, and develop the deep pattern recognition that transforms this problem from "something to memorize" into "something obvious."
By the end of this page, you will: (1) Deeply understand the mechanics of linked list reversal, (2) Implement reversal iteratively with O(1) space, (3) Implement reversal recursively and understand the call stack behavior, (4) Handle all edge cases confidently, (5) Recognize reversal as a component of more complex algorithms, (6) Understand when and why to reverse portions of a list.
Let's state the problem precisely:
Given: The head of a singly linked list.
Return: The head of the reversed list (which was previously the tail).
Constraint: The reversal must be performed in-place, meaning you cannot create a new list—you must modify the existing pointers.
Original: head → [1] → [2] → [3] → [4] → [5] → null
Reversed: head → [5] → [4] → [3] → [2] → [1] → null
Every arrow now points in the opposite direction. What was the tail (5) becomes the new head. What was the head (1) becomes the new tail, pointing to null.
Why is this hard?
With arrays, reversing is straightforward: swap the first and last elements, then the second and second-to-last, and so on. You have indices—random access is O(1).
With linked lists, you have none of that. Each node knows only its successor, not its predecessor. You can move forward, but never backward. To reverse, you must fundamentally rewire the structure—each node's next pointer must be changed to point to its previous node.
The challenge is doing this without losing track of the list. The moment you change node.next to point backward, you've severed the link to the next node. If you didn't store that reference first, it's gone forever.
| Aspect | Requirement |
|---|---|
| Input | Head pointer to a singly linked list |
| Output | Head pointer to the reversed list (previously the tail) |
| Space Complexity | O(1) for iterative, O(n) for recursive (call stack) |
| Time Complexity | O(n) — must visit each node exactly once |
| In-place? | Yes — no new nodes created, only pointer modifications |
| Destructive? | Yes — the original list structure is modified |
Before writing any code, let's build a deep mental model of what reversal actually means at the pointer level.
The Core Insight:
In a singly linked list, each node has a next pointer that points to its successor. Reversal means making each node's next pointer point to its predecessor instead. The first node becomes the last (points to null), and the last node becomes the first (becomes the new head).
Thinking About Individual Nodes:
Consider a single node in the middle of the list. Currently, it points forward to node B. After reversal, it must point backward to node A. But the node doesn't know about node A—that information existed only in A's pointer to it. This is the fundamental challenge: we need information that isn't directly available.
The solution emerges from a simple insight: if we maintain three pointers—previous, current, and next—we can preserve all the information we need. As we traverse, we save the next node before rewiring, then move all pointers forward. This pattern is the foundation of iterative reversal.
Walking Through the Logic:
null (the new tail will point to null)At each step:
next = curr.nextcurr.next = prevprev = currcurr = nextWhen curr becomes null, prev points to the new head (the old tail).
Why does this work?
By the time we modify curr.next, we've already saved the original next node. By the time we move forward, we've already updated prev to be curr. The chain reaction builds the reversed list behind us as we traverse forward.
| Step | prev | curr | next (saved) | Action | List State After |
|---|---|---|---|---|---|
| 0 (init) | null | [1] | — | Initialize pointers | 1 → 2 → 3 → null |
| 1 | null | [1] | [2] | save next, reverse [1].next | null ← 1 2 → 3 → null |
| 2 | [1] | [2] | [3] | save next, reverse [2].next | null ← 1 ← 2 3 → null |
| 3 | [2] | [3] | null | save next, reverse [3].next | null ← 1 ← 2 ← 3 |
| 4 | [3] | null | — | curr is null, done | head = [3] |
The iterative approach is the gold standard for linked list reversal in production code. It uses O(1) extra space (just three pointers) and processes each node exactly once, giving O(n) time complexity. It's also the most intuitive once you internalize the three-pointer pattern.
123456789101112131415161718192021222324252627282930313233343536373839404142
class ListNode: """Standard linked list node structure.""" def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list_iterative(head: ListNode) -> ListNode: """ Reverse a singly linked list iteratively. Time Complexity: O(n) - visits each node exactly once Space Complexity: O(1) - only uses three pointers Args: head: The head of the linked list Returns: The new head (previously the tail) """ # Edge case: empty list or single node if head is None or head.next is None: return head # Initialize our three pointers prev = None # Will become the new head curr = head # Current node being processed while curr is not None: # Step 1: Save the next node before we lose it next_temp = curr.next # Step 2: Reverse the pointer - this is the core operation curr.next = prev # Step 3: Move prev forward to current position prev = curr # Step 4: Move curr forward to the saved next node curr = next_temp # When loop ends, curr is None and prev is the new head return prevA common mistake is reversing the pointer before saving the next node. If you write curr.next = prev first, you've lost your only reference to the rest of the list. Always save next_temp = curr.next before modifying curr.next. This is a bug that compiles perfectly but produces incorrect results—only testing would catch it.
The recursive approach to reversal is elegant and demonstrates deep understanding of both recursion and linked list structure. However, it comes with a cost: O(n) space complexity due to the call stack. For very long lists, this could cause a stack overflow.
The Recursive Insight:
Recursion naturally processes nodes from tail to head (when the recursive call is made before the work). This is perfect for reversal—we want the tail to become the new head. The recursive approach reaches the end of the list first, then unwinds while setting up backward pointers.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
def reverse_list_recursive(head: ListNode) -> ListNode: """ Reverse a singly linked list recursively. Time Complexity: O(n) - visits each node exactly once Space Complexity: O(n) - recursive call stack depth The key insight: we recurse to the end first, then reverse pointers as the call stack unwinds. """ # Base case 1: empty list if head is None: return None # Base case 2: single node or we've reached the last node # This node (the original tail) becomes the new head if head.next is None: return head # Recursive case: reverse the rest of the list first # 'new_head' will be the tail, propagated back through all calls new_head = reverse_list_recursive(head.next) # Now we're unwinding. At this point: # - 'head' is the current node # - 'head.next' is the node that now needs to point back to 'head' # # Example: If list was 1 → 2 → 3, and we're at node 2: # - head = 2 # - head.next = 3 # - We need 3 to point to 2: head.next.next = head head.next.next = head # Make the next node point back to us head.next = None # Remove our forward pointer (we're now a tail or middle) # new_head is the original tail, always returned up the chain return new_head def reverse_list_recursive_traced(head: ListNode, depth: int = 0) -> ListNode: """ Same algorithm with tracing to visualize the recursion. """ indent = " " * depth print(f"{indent}reverse_list({head.val if head else None})") if head is None or head.next is None: print(f"{indent} Base case hit, returning {head.val if head else None}") return head print(f"{indent} Recursing to reverse rest of list...") new_head = reverse_list_recursive_traced(head.next, depth + 1) print(f"{indent} Unwinding: {head.next.val}.next = {head.val}") head.next.next = head head.next = None print(f"{indent} Returning new_head = {new_head.val}") return new_headUnderstanding the Unwinding Phase:
The magic of recursive reversal happens during the unwinding of the call stack. Let's trace through a small example: reversing 1 → 2 → 3.
3.next = 2 (3 now points to 2)2.next = null (2 no longer points forward)2.next = 1 (2 now points to 1)1.next = null (1 no longer points forward)Final list: 3 → 2 → 1 → null with head = 3
A truly robust implementation must handle all edge cases gracefully. Let's enumerate and address each one:
Edge Case 1: Empty List (head = null)
An empty list reversed is still an empty list. Both implementations handle this by returning null immediately.
Edge Case 2: Single Node
A list with one node is its own reverse. The head is also the tail, so we return it unchanged.
Edge Case 3: Two Nodes
The simplest non-trivial case. After reversal, A → B becomes B → A. This is often where bugs first appear.
Edge Case 4: Already Reversed (Idempotency)
Reversing a reversed list returns the original. Two reversals = identity. This is a useful property for testing.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
def test_reversal_edge_cases(): """Comprehensive test cases for linked list reversal.""" # Edge Case 1: Empty list result = reverse_list_iterative(None) assert result is None, "Empty list should return None" # Edge Case 2: Single node single = ListNode(42) result = reverse_list_iterative(single) assert result.val == 42, "Single node should be unchanged" assert result.next is None, "Single node should still point to None" # Edge Case 3: Two nodes # Create: 1 → 2 → None two_nodes = ListNode(1, ListNode(2)) result = reverse_list_iterative(two_nodes) assert result.val == 2, "Head should now be 2" assert result.next.val == 1, "Second node should be 1" assert result.next.next is None, "Tail should point to None" # Edge Case 4: Idempotency - double reversal # Create: 1 → 2 → 3 original = ListNode(1, ListNode(2, ListNode(3))) once = reverse_list_iterative(original) twice = reverse_list_iterative(once) # Verify: should be back to 1 → 2 → 3 assert twice.val == 1 assert twice.next.val == 2 assert twice.next.next.val == 3 # Edge Case 5: Large list (stress test) # Create list 1 → 2 → ... → 10000 head = ListNode(1) current = head for i in range(2, 10001): current.next = ListNode(i) current = current.next reversed_head = reverse_list_iterative(head) assert reversed_head.val == 10000, "New head should be 10000" # Verify last element is 1 curr = reversed_head while curr.next: curr = curr.next assert curr.val == 1, "Tail should be 1" print("All edge case tests passed! ✓")In languages like C or C++, improper reversal can lead to memory leaks. If you lose a reference to a node during reversal, you can never free that memory. In garbage-collected languages (Python, Java, JavaScript), lost nodes are eventually cleaned up—but the bug still produces incorrect results. Always verify your pointer assignments carefully.
A natural extension of full reversal is partial reversal: reversing only a section of the list between positions left and right. This is a common interview problem and a building block for algorithms like "Reverse Nodes in k-Group."
The Challenge:
You can't just reverse the middle nodes—you must also reconnect the reversed section to the surrounding parts of the list. This requires carefully tracking:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
def reverse_between(head: ListNode, left: int, right: int) -> ListNode: """ Reverse nodes from position 'left' to 'right' (1-indexed). Example: 1 → 2 → 3 → 4 → 5, left=2, right=4 Result: 1 → 4 → 3 → 2 → 5 Time Complexity: O(n) Space Complexity: O(1) """ if not head or left == right: return head # Use a dummy node to handle edge case where left=1 dummy = ListNode(0) dummy.next = head # Step 1: Navigate to the node just before the reversal section pre = dummy for _ in range(left - 1): pre = pre.next # 'pre' is now the node before position 'left' # 'cur' is the first node to be reversed cur = pre.next # Step 2: Reverse nodes one by one using the "insert at front" technique # We repeatedly move the next node to just after 'pre' for _ in range(right - left): # 'temp' is the node we're moving temp = cur.next # Remove 'temp' from its position cur.next = temp.next # Insert 'temp' right after 'pre' temp.next = pre.next pre.next = temp return dummy.next def reverse_between_standard(head: ListNode, left: int, right: int) -> ListNode: """ Alternative: Use standard reversal approach on the sublist. """ if not head or left == right: return head dummy = ListNode(0) dummy.next = head # Navigate to node before reversal section pre = dummy for _ in range(left - 1): pre = pre.next # Standard reversal pointers prev = None curr = pre.next # Reverse 'right - left + 1' nodes for _ in range(right - left + 1): next_temp = curr.next curr.next = prev prev = curr curr = next_temp # Reconnect: # pre.next was the first node of section, now it's the last # prev is the new first node of section # curr is the node after the section pre.next.next = curr # Connect old first (new last) to rest of list pre.next = prev # Connect pre to new first (old last) return dummy.nextWhen the reversal might affect the head of the list (when left=1), a dummy node simplifies the logic. It gives us a stable 'pre' node even when reversing from the very beginning. This technique appears in many linked list problems and is worth memorizing.
List reversal isn't just a standalone problem—it's a fundamental operation used in many advanced algorithms. Recognizing when reversal is part of a larger solution is a key problem-solving skill.
Pattern Recognition Exercise:
When you encounter a linked list problem, ask yourself:
If any answer is yes, reversal might be part of your solution.
| Problem Type | Reversal Role | Example |
|---|---|---|
| Comparison problems | Reverse one half to enable linear comparison | Palindrome linked list |
| Reordering problems | Reverse to change processing order | Reverse nodes in k-group |
| Mathematical operations | Reverse to align digits | Add two numbers |
| Positional access | Reverse to access from the "end" | Kth node from end |
| Structural transformation | Reverse segments for required pattern | Reorder list |
Let's rigorously analyze why our reversal algorithms achieve the best possible complexity bounds.
Time Complexity: O(n)
We must visit every node exactly once to reverse the list—there's no way around this. Each node's pointer needs to be modified, and you can't modify something without accessing it. Thus, O(n) time is both achieved and optimal.
Space Complexity: O(1) Iterative vs O(n) Recursive
The iterative approach uses only three pointers regardless of list length—constant space.
The recursive approach uses O(n) space because each recursive call adds a stack frame. For a list of n nodes, we make n recursive calls before hitting the base case. Each stack frame stores local variables and the return address.
| Approach | Time | Space | Stack Safety | Production Use |
|---|---|---|---|---|
| Iterative | O(n) | O(1) | Always safe | Preferred |
| Recursive | O(n) | O(n) | Risk overflow | Limited |
| Tail Recursive* | O(n) | O(1)** | Depends on language | Rare |
** With TCO, the recursive version could achieve O(1) space, but don't rely on this.
Why Can't We Do Better Than O(n) Time?
To reverse a list, we must:
No matter how clever we are, these are irreducible. We can't skip nodes—each one is part of the chain. We can't avoid modifications—each pointer must change direction. O(n) is the lower bound, and we achieve it.
The Importance of O(1) Space:
In systems handling very long lists (millions of nodes), O(n) space for the recursive approach could mean hundreds of megabytes of stack usage. The iterative approach uses the same three pointers whether the list has 3 nodes or 3 million. This scalability is why iterative reversal is the industry standard.
Even experienced developers make mistakes when reversing linked lists. Here are the most common errors and how to prevent them:
curr.next = prev, the original curr.next is lost forever unless you saved it first.curr is null. The new head is prev, not curr. Returning curr gives you null.curr = curr instead of curr = next_temp, you'll loop forever on the same node.head.next.next = head, you must set head.next = null. Otherwise you create a cycle.When your reversal code produces wrong results, draw the list state at each step. Use a 3-node list (1 → 2 → 3) and trace through manually. This usually reveals exactly where your pointer assignments go wrong. Automated tests catch bugs; manual tracing explains them.
Linked list reversal is a gateway pattern—mastering it unlocks understanding of many other algorithms. Let's consolidate what we've learned:
Practice Strategy:
Reverse a linked list until you can write it without thinking. Then solve problems that use reversal as a component: palindrome detection, reverse-in-groups, reorder list. This progression builds the pattern recognition that makes linked list problems feel routine.
What's Next:
In the next page, we'll explore merging sorted linked lists—another fundamental pattern that combines traversal, comparison, and pointer manipulation into an elegant algorithm used throughout computer science.
You've mastered linked list reversal—the gateway pattern for linked list expertise. You understand both iterative and recursive approaches, can handle edge cases, and recognize reversal as a building block for more complex algorithms. Practice until this pattern becomes automatic.