Reverse Linked List

You'll reverse a linked list in place by flipping one next link at a time. You need linked list nodes and assignment. Related chapter: linked lists.

1. The problem

You get the head of a linked list. Reverse it by changing its next links, and return the new head. Reuse the original nodes; don't just return the values in reverse. An empty list returns None. This is LeetCode 206.

2. A correct baseline

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

def build(values):
    head=None
    for value in reversed(values):
        head=ListNode(value,head)
    return head

def nodes(head):
    result=[]
    while head:
        result.append(head)
        head=head.next
    return result

def values(head):
    return [node.val for node in nodes(head)]

def baseline(head):
    original=nodes(head)
    for i,node in enumerate(original):
        node.next=original[i-1] if i else None
    return original[-1] if original else None

assert values(baseline(build([1,2,3])))==[3,2,1]
assert values(baseline(build([7])))==[7]
assert baseline(None) is None

This takes O(n) time, but also O(n) extra space to keep a list of every node. On a million nodes, that's a million extra references.

The bottleneck. It stores every node, but at any moment you only need two things: the part already reversed, and the next node to read.

3. The observation

Picture 1 → 2 → 3 halfway through: 2 → 1 → None is reversed, and 3 is still waiting. To move 3 over, point it at 2. Then the reversed part is 3 → 2 → 1 → None.

So keep two pointers: previous, the head of the reversed part, and current, the next node to move. For each node, point it back at previous. But save current.next first. Once you overwrite it, you've lost the only link to the rest of the list.

4. The solution and a trace

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

class Solution:
    def reverseList(self, head):
        """Reverse an acyclic singly linked list, reusing every node."""
        previous=None
        current=head
        while current:
            following=current.next  # Save the unread suffix before rewiring.
            current.next=previous
            previous=current
            current=following
        return previous

solve=Solution().reverseList
assert values(solve(build([1,2,3])))==[3,2,1]
assert values(solve(build([7])))==[7]
assert solve(None) is None

Trace 1 → 2 → 3:

5. Why it works

What stays true. previous is the head of the reversed part, and current is the head of the part still to read.

Why each step keeps it true. Saving following keeps the rest of the list reachable. Pointing current at previous moves exactly one node into the reversed part.

The result is right. Each node moves once. When current is None, every node is in the reversed part, and previous is its head.

6. Cost, edge cases, and failure

Cost. One pass: O(n) time, growing in step with the list. O(1) extra space, for three pointers.

Edge cases. The nodes and their values stay the same; only the next links change. Empty and one-node lists need no special handling. A list with a cycle has no end, so it can't be reversed this way.

Where it fails. Swapping values instead of links would return the old head with new values. The test checks that the actual nodes moved:

head=build([1,2]); first=head; second=head.next
result=solve(head)
assert result is second and result.next is first and first.next is None

import random
rng=random.Random(206)
for _ in range(500):
    data=[rng.randint(-10,10) for _ in range(rng.randrange(50))]
    head=build(data); original=nodes(head)
    result=solve(head); actual=nodes(result)
    assert actual==original[::-1]
    assert [n.val for n in actual]==values(baseline(build(data)))
# The iterative solution also handles chains beyond Python's recursion depth.
assert len(nodes(solve(build(list(range(5000))))))==5000