Solving Reverse a Linked List in Python: Step-by-Step Guide

Reversing a linked list is one of the most classic problems in computer science and a frequent guest in technical interviews. While the problem sounds simple on the surface, it forces you to deeply understand pointers, references, and how nodes connect to one another. In this tutorial, we will walk through what a linked list is, why reversing it matters, and how to implement the solution in Python using both iterative and recursive approaches.

What Is a Linked List?

A linked list is a linear data structure where elements, called nodes, are stored in non-contiguous memory locations. Each node contains two parts: a value (the data) and a next reference (a pointer to the next node in the sequence). Unlike arrays, linked lists do not provide random access to elements, which means traversal must happen sequentially starting from the head node.

Here is a minimal definition of a singly linked list node in Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Given a list like 1 -> 2 -> 3 -> 4 -> None, reversing it means producing 4 -> 3 -> 2 -> 1 -> None. The head of the original list becomes the tail, and the original tail becomes the new head.

Why Reversing a Linked List Matters

You might wonder why this specific operation deserves so much attention. There are several reasons:

Interview relevance: It tests your understanding of references and edge cases, making it a staple in coding interviews at companies like Google, Amazon, and Microsoft.
Foundational skill: Mastering pointer manipulation builds the mental model you need for more complex structures like trees and graphs.
Real-world use cases: Reversing is used in palindrome detection, undo functionality, browser history navigation, and certain arithmetic operations on big numbers stored as lists.
Algorithm building block: Many advanced problems, such as reversing a sublist or rotating a list, build directly on this technique.

How to Reverse a Linked List Iteratively

The iterative approach is the most common and efficient solution. The idea is to traverse the list once while flipping each node's next pointer to point to the previous node instead of the next one. We maintain three pointers during traversal: prev, current, and next_node.

The algorithm works as follows:

Initialize prev to None (this will become the new tail's next pointer).
Set current to the head of the list.
While current is not None, temporarily store the next node, redirect current.next to prev, then advance both prev and current one step forward.
When the loop ends, prev points to the new head.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_list(head):
    prev = None
    current = head

    while current is not None:
        next_node = current.next   # store the next node
        current.next = prev        # reverse the pointer
        prev = current             # move prev forward
        current = next_node        # move current forward

    return prev  # prev is the new head


# Helper to build a list from a Python list
def build_list(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next


# Helper to print a list
def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) + " -> None")


# Example usage
head = build_list([1, 2, 3, 4, 5])
print("Original:")
print_list(head)

reversed_head = reverse_list(head)
print("Reversed:")
print_list(reversed_head)

Running this code produces:

Original:
1 -> 2 -> 3 -> 4 -> 5 -> None
Reversed:
5 -> 4 -> 3 -> 2 -> 1 -> None

The iterative solution runs in O(n) time, where n is the number of nodes, and uses O(1) extra space because we only store a few pointers regardless of list size.

How to Reverse a Linked List Recursively

The recursive approach is elegant but slightly trickier. The idea is to recursively reach the end of the list, then on the way back up the call stack, reverse each pointer. The base case returns the last node, which becomes the new head. As each recursive call returns, we set current.next.next = current to flip the pointer, and then set current.next = None to break the old link.

def reverse_list_recursive(head):
    # Base case: empty list or single node
    if head is None or head.next is None:
        return head

    # Recursively reverse the rest of the list
    new_head = reverse_list_recursive(head.next)

    # Reverse the pointer between the next node and current node
    head.next.next = head
    head.next = None

    return new_head


# Example usage
head = build_list([1, 2, 3, 4, 5])
print("Original:")
print_list(head)

reversed_head = reverse_list_recursive(head)
print("Reversed (recursive):")
print_list(reversed_head)

The recursive version also runs in O(n) time, but it uses O(n) space on the call stack due to the recursive calls. For very long lists, this can cause a stack overflow, which is why the iterative approach is generally preferred in production code.

Handling Edge Cases

A robust solution must handle several edge cases gracefully. Always test your implementation against the following scenarios:

Empty list: The head is None. Both implementations return None immediately.
Single node: A list with one node is its own reverse. The recursive base case handles this directly, and the iterative loop simply does not execute.
Two nodes: The simplest non-trivial case. Verify that the pointers swap correctly.
Large lists: For the recursive approach, watch out for Python's default recursion limit (usually 1000). Use sys.setrecursionlimit() only if absolutely necessary, or prefer the iterative version.

Here is a quick test harness that covers these cases:

def test_reverse():
    # Empty list
    assert reverse_list(None) is None

    # Single node
    single = ListNode(1)
    result = reverse_list(single)
    assert result.val == 1 and result.next is None

    # Two nodes
    two = build_list([1, 2])
    result = reverse_list(two)
    assert result.val == 2 and result.next.val == 1 and result.next.next is None

    # General case
    general = build_list([1, 2, 3, 4, 5])
    result = reverse_list(general)
    assert result.val == 5

    print("All tests passed.")


test_reverse()

Best Practices

When implementing or using linked list reversal in real projects, keep the following best practices in mind:

Prefer the iterative approach: It avoids recursion depth issues and is more memory efficient.
Use clear variable names: Names like prev, current, and next_node make the logic self-documenting.
Draw the pointers: When debugging, sketch the nodes and arrows on paper. Pointer bugs are much easier to spot visually.
Test with small examples first: Trace through a two- or three-node list by hand before running larger inputs.
Watch for cycles: If the input list might contain a cycle, detect it first with Floyd's algorithm before attempting a reversal.
Consider in-place reversal: Avoid creating new nodes unless the problem explicitly requires a copy. In-place reversal is faster and uses less memory.
Document the return value: Clearly state that the function returns the new head, since the original head reference passed in is no longer the front of the list.

Variations You May Encounter

Once you understand the basic reversal, several related problems become much easier:

Reverse a sublist: Reverse only nodes between positions m and n. This requires careful pointer bookkeeping at the boundaries.
Reverse in k-groups: Reverse nodes in chunks of size k. This combines reversal with grouping logic.
Doubly linked list reversal: Each node has both next and prev pointers, so you must swap both.
Palindrome check: Reverse the second half of the list and compare it with the first half.

Here is a brief example of reversing a doubly linked list for reference:

class DoublyListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


def reverse_doubly_list(head):
    current = head
    new_head = None

    while current is not None:
        # Swap prev and next pointers
        current.prev, current.next = current.next, current.prev
        new_head = current
        # Because we swapped, move to the old next (now in prev)
        current = current.prev

    return new_head

Conclusion

Reversing a linked list is a deceptively simple problem that teaches fundamental lessons about pointer manipulation, memory references, and algorithm design. The iterative solution is efficient, easy to reason about, and safe for lists of any size, while the recursive solution offers an elegant alternative that reinforces your understanding of the call stack. By mastering both approaches, handling edge cases carefully, and following best practices, you will be well prepared not only for coding interviews but also for the many real-world scenarios where linked list manipulation plays a role. Practice the variations mentioned above to deepen your skills, and always remember to trace through small examples by hand before trusting your code on larger inputs.