Editor

Reverse a linked list in Python

A linked list is a chain of nodes where each node points to the next one. Reversing it turns every arrow around, one node at a time, while holding on to the rest of the chain so nothing is lost.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. prev starts as None and current starts at the head, node 1.
  2. Save current.next in next_node first, or the rest of the list would be lost.
  3. Point current.next back at prev, then move prev and current one node forward.
  4. When current becomes None, prev holds the old tail, which is the head of the reversed list.

What to watch

  • Watch the next arrows turn around one node at a time.
  • Watch next_node: right after current.next changes, it is the only thing still pointing at the rest of the list.
  • Watch node 1: its next becomes None, so the old head is now the tail.

The code

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

def reverse(head):
    prev = None
    current = head
    while current:
        next_node = current.next   # remember the rest of the list
        current.next = prev        # turn this arrow around
        prev = current
        current = next_node
    return prev                    # the old tail is the new head

def show(head):
    values = []
    while head:
        values.append(str(head.value))
        head = head.next
    return " -> ".join(values)

head = Node(1, Node(2, Node(3, Node(4))))
print("Before:", show(head))
print("Reversed:", show(reverse(head)))
Output
Before: 1 -> 2 -> 3 -> 4
Reversed: 4 -> 3 -> 2 -> 1

Open it in the editor · Python Program to Implement a Linked List, explained