DSA Reversing a Linked List

The problem

A linked list is a chain of nodes where each node holds a value and a link named next to the following node. The last node links to None. Reversing the list flips every link, so the chain runs backwards.

The answer is the head of the reversed chain. The values themselves never move. Only the links change direction, and the cases below print each chain before its answer is expected.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

cases = [([1, 2, 3, 4], "4 -> 3 -> 2 -> 1 -> None"), ([1, 2], "2 -> 1 -> None"), ([7], "7 -> None"), ([], "None")]
for values, expected in cases:
    print("list", render(build(values)), "- reversed:", expected)

Read one row at a time. The old tail becomes the new head. The old head becomes the new tail, and its link ends at None.

Intuition: copy the values out and rebuild

The first idea reads every value into a plain Python list. The values then get reversed there, where reversing is easy. A fresh chain is built from the reversed values.

The result is correct. The cost is the trap. Every value is stored a second time, and every node is created a second time, to achieve what is only a change of link direction.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

head = build([1, 2, 3, 4])
values = []
node = head
while node is not None:
    values.append(node.value)
    node = node.next
values.reverse()
rebuilt = build(values)
print("reversed:", render(rebuilt))
print("values stored a second time:", len(values))

Four nodes cost four extra stored values and four brand-new nodes. A chain of a million nodes pays both costs a million times. The links were the only thing that needed to change.

Brute force: rebuild by pushing each value at the front

The brute force avoids the intermediate reversed list. Each value read from the old chain becomes a new node pushed onto the front of a new chain. Front-pushing reverses the order for free.

The method still builds a second chain. The counter below charges one unit per new node created. The old chain is left untouched, which is exactly the waste the optimal method removes.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

head = build([1, 2, 3, 4])
new_head = None
created = 0
node = head
while node is not None:
    fresh = Node(node.value)
    created += 1
    fresh.next = new_head
    new_head = fresh
    node = node.next
print("reversed:", render(new_head))
print("new nodes created:", created)
print("original still intact:", render(head))

The printed original proves the cost. Two full chains exist where one would do. The reversal needed four link changes, and this method instead did four allocations plus four reads.

The optimal solution: flip each link in place

Three pointers named prev, curr and nxt flip each link in place during one walk, and prev ends on the new head. That one sentence is the whole method.

The pointer nxt saves the rest of the chain before curr's link flips. Without that save, flipping the link would strand every unvisited node. The pointer prev starts at None, because the old head becomes the new tail and a tail links to None.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

def reverse(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

cases = [([1, 2, 3, 4], "4 -> 3 -> 2 -> 1 -> None"), ([1, 2], "2 -> 1 -> None"), ([7], "7 -> None"), ([], "None")]
for values, expected in cases:
    result = render(reverse(build(values)))
    print("list", values, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. No new node is created anywhere in the function. The same nodes carry the reversed chain, in reversed order.

Walkthrough: reversing [1, 2, 3]

Three nodes need three flips. The state after each flip has two chains. One chain hangs from prev, already reversed, and the other hangs from curr, still in its original order.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

head = build([1, 2, 3])
prev = None
curr = head
step = 0
while curr is not None:
    nxt = curr.next
    curr.next = prev
    step += 1
    prev = curr
    curr = nxt
    print("after flip", step, "- reversed part:", render(prev), "| remaining:", render(curr))
head = prev
print("final:", render(head))

The reversed part grows by one node per flip. The remaining part shrinks by one node per flip. The walk ends when the remaining part is just None, and prev then heads the full reversed chain.

Complexity

The walk visits each node once and flips one link per visit, so its time is O(n) for n nodes. The brute-force rebuilds also take O(n) time, because each one reads every value and builds every node once.

The in-place walk stores three pointers and nothing per node, so its extra space is O(1). Both rebuild methods store a second copy of the data, so their extra space is O(n).

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

def reverse(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

for values in [[1, 2, 3, 4], list(range(1, 9)), list(range(1, 17))]:
    head = build(values)
    flips = 0
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        flips += 1
        prev = curr
        curr = nxt
    print("nodes:", len(values), "- flips:", flips, " new nodes created: 0")

Counts beat clocks here. The flip count equals the node count at every size. The new-node count stays at zero, which is the whole advantage in one column.

Edge cases and pitfalls

Losing the saved nxt link is the fatal mistake. The flip overwrites curr.next, and nxt is the only reference to the unvisited rest. One flip without the save loses the whole remainder of the chain.

Returning the wrong pointer is the quieter mistake. The variable head still points at the old head, which is now the tail. The function must return prev, the last node the walk visited.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)

def reverse(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

print("empty list:", render(reverse(build([]))))
print("single node:", render(reverse(build([7]))))
print("two nodes:", render(reverse(build([1, 2]))))
print("duplicate values:", render(reverse(build([5, 5, 1]))))
head = build([1, 2, 3])
head = reverse(head)
print("reversed once:", render(head))
head = reverse(head)
print("reversed twice, back to start:", render(head))

Reversing twice restores the original chain exactly. Each flip is its own undo. That symmetry is a quick self-check for any reversal code.