Reversing a Linked List - Common Linked List Patterns & Problem Types | OneNoughtOne

0/361

Data Structures & AlgorithmsCommon Linked List Patterns & Problem Types

Common Linked List Patterns & Problem Types

LevelIntermediate

Duration120 mins

TopicCommon Linked List Patterns & Problem Types

1 / 5

Reversing a Linked List

The Gateway Pattern

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."

What You Will Learn

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.

The Problem Statement

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.

Visual Transformation

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.

Reversal Requirements Summary
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

Conceptual Foundation — Understanding the Inversion

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 Three-Pointer Pattern

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:

prev starts as null (the new tail will point to null)
curr starts at the head
next is temporarily stored before we modify curr.next

At each step:

Save the next node: next = curr.next
Reverse the pointer: curr.next = prev
Move prev forward: prev = curr
Move curr forward: curr = next

When 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.

Pointer States During Reversal of [1] → [2] → [3] → null
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]

Iterative Implementation — The Industry Standard

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.

reverse_linked_list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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 prev

The Order of Operations Matters

A 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.

Recursive Implementation — Elegant but Space-Intensive

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.

reverse_linked_list_recursive.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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_head

Understanding 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.

Call reverse(1) — not base case, recurse on 2
Call reverse(2) — not base case, recurse on 3
Call reverse(3) — base case! 3 has no next. Return 3 as new_head
Unwind to reverse(2): new_head = 3
- head = 2, head.next = 3
- Execute: 3.next = 2 (3 now points to 2)
- Execute: 2.next = null (2 no longer points forward)
- Return new_head (still 3)
Unwind to reverse(1): new_head = 3
- head = 1, head.next = 2
- Execute: 2.next = 1 (2 now points to 1)
- Execute: 1.next = null (1 no longer points forward)
- Return new_head (still 3)

Final list: 3 → 2 → 1 → null with head = 3

Recursive Advantages

•Code is more concise and elegant
•Naturally models the problem structure
•Easier to extend to partial reversal
•Great for understanding recursion deeply
•Cleaner for reversing sublists

Recursive Disadvantages

•O(n) space from call stack
•Risk of stack overflow for long lists
•Harder to trace for beginners
•Slower due to function call overhead
•Less commonly used in production

Edge Cases and Robustness

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.

edge_cases_test.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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! ✓")

Memory Safety in Low-Level Languages

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.

Partial Reversal — Reversing Between Positions

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:

The node before the reversal section
The first node of the section (which becomes the last after reversal)
The last node of the section (which becomes the first after reversal)
The node after the reversal section

reverse_between.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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.next

The Dummy Node Technique

When 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.

Reversal as a Building Block for Other Algorithms

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.

Algorithms That Use Reversal

•Palindrome Detection — Reverse the second half, compare to first half. If they match, it's a palindrome. (We'll cover this in detail later in this module.)
•Reverse Nodes in k-Group — Reverse every k consecutive nodes. Uses partial reversal repeatedly.
•Alternating Reversal — Reverse every other group or segment. Common in interview problems.
•Adding Two Numbers (Reversed) — When numbers are stored in reverse order, you add digit-by-digit from head. If stored normally, reverse first.
•Rotate List — Rotating a list by k positions can be done by reversing segments.
•Reorder List — Interleave first and reversed second half (L1 → Ln → L2 → Ln-1 → ...).

Pattern Recognition Exercise:

When you encounter a linked list problem, ask yourself:

Does the problem require processing nodes in reverse order?
Would reversing a portion simplify comparisons or reordering?
Is there a "from the end" component (like "kth from end")?

If any answer is yes, reversal might be part of your solution.

Problem Recognition Guide
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

Complexity Analysis — Why Reversal is Optimal

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.

Complexity Comparison
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

Tail Call Optimization

Some languages (Scheme, Scala, optimized C compilers) support tail call optimization, where a tail-recursive function can be converted to iteration by the compiler. However, Python, Java, and most JavaScript implementations do NOT support this. Thus, for portability, the iterative approach remains superior.

** 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:

Visit every node (n visits minimum)
Modify every pointer (n modifications minimum)

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.

Common Mistakes and How to Avoid Them

Even experienced developers make mistakes when reversing linked lists. Here are the most common errors and how to prevent them:

Classic Mistakes in Linked List Reversal

•Forgetting to save next before modifying — The most common bug. Once you set curr.next = prev, the original curr.next is lost forever unless you saved it first.
•Returning the wrong node — After the loop, curr is null. The new head is prev, not curr. Returning curr gives you null.
•Not handling edge cases — Empty lists and single-node lists should return immediately. Forgetting these checks can cause null pointer exceptions.
•Infinite loops — If you accidentally set curr = curr instead of curr = next_temp, you'll loop forever on the same node.
•Off-by-one errors in partial reversal — Position counting is tricky. Using 0-indexed vs 1-indexed positions causes off-by-one bugs. Be explicit about your indexing convention.
•Forgetting to set old head's next to null (recursive) — In recursive reversal, after head.next.next = head, you must set head.next = null. Otherwise you create a cycle.

Debugging Strategy

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.

Summary: Mastering Linked List Reversal

Linked list reversal is a gateway pattern—mastering it unlocks understanding of many other algorithms. Let's consolidate what we've learned:

Key Takeaways

•The three-pointer technique (prev, curr, next) is the foundation of iterative reversal. Save next before modifying, then advance all pointers.
•Recursive reversal is elegant but uses O(n) stack space. It processes nodes from tail to head during unwinding.
•Edge cases (empty list, single node) must be handled explicitly to avoid null pointer errors.
•Partial reversal extends the basic pattern by tracking connection points before and after the reversed section.
•Reversal appears in many advanced algorithms — palindrome detection, k-group reversal, list reordering, and more.
•The iterative approach is preferred in production due to O(1) space and no risk of stack overflow.

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.

Page Complete

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.