Reverse Linked List — LeetCode Solution in Python

The problem, in short

You are given the head of a singly linked list, where each node holds a value and a pointer to the next node. Reverse the direction of every link so the last node becomes the head, and return the new head.

An empty list, or a list with one node, is returned unchanged.

How to think about it

Reversing a linked list is not about moving values — it is about turning arrows round. Each node's next pointer should point at the node that currently precedes it.

The difficulty is that the moment you overwrite node.next, you have lost your only route to the rest of the list. A singly linked list gives you no way back. So the whole technique comes down to one rule: save the next node before you break the link. That is why the iterative solution needs three pointers — the node behind, the node you are on, and a temporary hold on the node ahead.

The brute-force approach

A tempting shortcut is to copy the values into a Python list, reverse it, and write them back into the nodes.

def reverse_list_values(head):
    values, node = [], head
    while node:
        values.append(node.val)
        node = node.next

    node = head
    for value in reversed(values):
        node.val = value
        node = node.next

    return head

It produces the right sequence, but it sidesteps what the problem is actually testing: pointer manipulation. It also needs two passes and O(n) extra memory, and it mutates every node's value rather than relinking — which breaks if other code holds references to those nodes.

The optimised approach

Walk the list once with two pointers, previous and current. At each node: stash current.next, point current.next backwards at previous, then shuffle both pointers one step forward. When current falls off the end, previous is sitting on the last node — the new head.

previous starts as None, which is exactly right: the old head must end up pointing at nothing, and it gets that for free on the first iteration.

Python solution

def reverse_list(head):
    """Reverse a singly linked list in place and return the new head."""
    previous = None
    current = head

    while current:
        upcoming = current.next      # save the way forward BEFORE breaking it
        current.next = previous      # turn the arrow round
        previous = current           # shuffle both pointers along
        current = upcoming

    return previous                  # current is None; previous is the last node

The recursive version

The same idea expressed as recursion: reverse everything after the head, then make the node after the head point back at the head.

def reverse_list_recursive(head):
    # Base case: empty list, or we have reached the final node.
    if head is None or head.next is None:
        return head

    new_head = reverse_list_recursive(head.next)

    head.next.next = head    # the node ahead now points back at us
    head.next = None         # and we point at nothing

    return new_head          # unchanged all the way back up the call stack

head.next.next = head is the line worth pausing on. At that point head.next is still the original next node — now the tail of the reversed remainder — so pointing its next at head appends the current node to the end. Setting head.next = None then avoids leaving a cycle between the two nodes.

Time and space complexity

Every node is visited exactly once and the work at each node is a fixed number of pointer assignments, so the time is linear. Only three pointers exist regardless of list length, so the space is constant. The recursive version above is also O(n) time but costs O(n) stack space, which is why the iterative form is the one to reach for on a long list.

Example walkthrough

Take the list 1 → 2 → 3 → None.

The loop ends because current is None. previous holds node 3, which is the new head.

Common mistakes

1. Overwriting next before saving it. Writing current.next = previous without stashing upcoming first discards the rest of the list. You end up with a two-node result and no way to reach the others.
2. Returning head instead of previous. After the loop, head is the last node of the reversed list and its next is None, so returning it gives a one-node list. The new head is previous.
3. Forgetting head.next = None in the recursive version. Without it, the first two nodes point at each other and the list contains a cycle — anything that walks it afterwards hangs forever.
4. Assuming a non-empty list. reverse_list(None) must return None. The iterative version handles it naturally; make sure the recursive base case tests head is None as well as head.next is None.

Related problems

• Reverse Linked List II — Reversing only the section between two positions.
• Palindrome Linked List — Reverse the second half, then compare — this problem used as a step.
• Merge Two Sorted Lists — The other core pointer-rewiring exercise.

More write-ups are indexed in Boopathi's LeetCode solutions.