Reversing a Linked List

You need three pointers: the node you are currently on, the node you have already processed, and the node that is coming next. At each step you save the next node, point the current node backwards at the previous one, and then advance. The head of the reversed list is the last node you process.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


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


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out


def reverse(head):
    previous = None
    current = head
    while current:
        following = current.next
        current.next = previous
        previous = current
        current = following
    return previous


print(to_list(build([1, 2, 3, 4, 5])))
print(to_list(reverse(build([1, 2, 3, 4, 5]))))

The outputs are 1, 2, 3, 4, 5 and 5, 4, 3, 2, 1. The list itself is reversed in place, so no new nodes are allocated and the original list object is the one being changed.

The mechanism is that saving the next pointer before overwriting it is what keeps the rest of the list reachable. Without that save, the moment you set the current node's next to the previous node you lose the remainder of the list. The invariant that holds throughout is that previous points at the reversed prefix and current points at the first node of the untouched suffix.

The trade-off to name is the dummy head problem. The iterative version returns the new head explicitly, which means the caller has to use the return value rather than trusting the argument. A version that installs a dummy node before the real head avoids that, at the cost of one extra node. Both are O of n time and O of 1 space, and the iterative version is preferable whenever the list is long, because the recursive version in the next answer uses stack space proportional to the length and will overflow on a very long list.

The recursive version reverses the list after the first node. Reverse the rest of the list, then make the node after the head point back at the head and cut the head's own pointer, so the head becomes the tail of the reversed list.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


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


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out


def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


print(to_list(reverse_recursive(build([1, 2, 3, 4, 5]))))

The output is 5, 4, 3, 2, 1. The base case is a list of zero or one node, which is already its own reverse.

The mechanism is that the recursion does the hard part first. By the time the call for the head returns, the entire rest of the list has been reversed, so the node that used to follow the head is now the head of the reversed list. Linking it back to the current head and then detaching the head's own pointer puts the current node at the tail.

The trade-off to name is the stack. The recursion nests one level per node, so a list of a hundred thousand nodes will exhaust the Python stack, while the iterative version has no such limit and uses a fixed amount of memory. The recursive version is still worth knowing because it expresses the idea in three lines, and because the same shape of reasoning appears in problems like flattening a nested list or reversing a sublist.

Find the node just before the block, then reverse the block in isolation and reconnect both ends. Using a dummy node before the head keeps the position arithmetic uniform, which matters when the block starts at the first node.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


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


def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out


def reverse_between(head, left, right):
    if not head or left >= right:
        return head
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    block_head = before.next
    current = block_head
    previous = None
    for _ in range(right - left + 1):
        following = current.next
        current.next = previous
        previous = current
        current = following
    block_head.next = current
    before.next = previous
    return dummy.next


print(to_list(reverse_between(build([1, 2, 3, 4, 5]), 2, 4)))

The output is 1, 4, 3, 2, 5. The block from position two to position four, which was 2, 3, 4, is now 4, 3, 2, and everything outside it is untouched.

The three pointer assignments at the end are the whole trick. The old head of the block now becomes the tail of the reversed block, so it must point at whatever followed the block, which is the node currently held in current. The node before the block must point at the new head of the block, which is previous.

The mechanism is that reversing a sublist is the same as reversing the whole list, except that the final links are not left dangling. The loop walks exactly the number of nodes in the block, so current ends up pointing at the first node after the block and previous at the last node of the reversed block.

The trade-off to name is bookkeeping. Reversing a sublist has more moving parts than reversing the whole list, and the order of the two reconnections matters. Get them the wrong way round and you create a cycle in the list, which is a failure mode that is easy to miss in a test and hard to debug later. Working with a dummy node removes the special case where the block starts at the head, which is why it is used here and in most production implementations of this pattern.