In-place linked list reversal in Python
Reverse a singly linked list in O(n) time and O(1) extra space by re-pointing each node.
- File
reverse_linked_list.py, 55 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/reverse-linked-list/. The authors are listed in prov/X89XHB.jsonl.
from typing import Generic, Iterable, TypeVar
T = TypeVar("T")
class Node(Generic[T]):
"""A node of a singly linked list: a value and a pointer to the next node."""
__slots__ = ("value", "next")
def __init__(self, value: T, next: "Node[T] | None" = None) -> None:
self.value = value
self.next = next
def from_iterable(items: Iterable[T]) -> Node[T] | None:
"""Build a list with the items in order and return its first node, or None."""
head: Node[T] | None = None
tail: Node[T] | None = None
for x in items:
node = Node(x)
if tail is None:
head = node
else:
tail.next = node
tail = node
return head
def to_list(head: Node[T] | None) -> list[T]:
"""Return the values of the list that starts at head, in order."""
out: list[T] = []
while head is not None:
out.append(head.value)
head = head.next
return out
def reverse(head: Node[T] | None) -> Node[T] | None:
"""Reverse the list that starts at head in place and return the new first node.
Precondition: the list has no cycle. The nodes are reused and the old
list is destroyed. Cost: Theta(n) time, Theta(1) extra space, n writes.
"""
prev: Node[T] | None = None # @line L1
curr = head # @line L2
while curr is not None: # @line L3
nxt = curr.next # @line L4
curr.next = prev # @line L5
prev = curr # @line L6
curr = nxt # @line L7
return prev # @line L8
test_reverse_linked_list.py 52 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/reverse-linked-list/. The authors are listed in prov/X89XHB.jsonl.
import random
from reverse_linked_list import Node, from_iterable, reverse, to_list
def nodes_of(head: Node[int] | None) -> list[Node[int]]:
out = []
while head is not None:
out.append(head)
head = head.next
return out
def test_example() -> None:
head = from_iterable([1, 2, 3, 4, 5])
assert to_list(reverse(head)) == [5, 4, 3, 2, 1]
def test_edges() -> None:
assert reverse(None) is None
one = Node(7)
assert reverse(one) is one and one.next is None
two = from_iterable([1, 2])
r = reverse(two)
assert to_list(r) == [2, 1]
assert two is not None and two.next is None # the old head is now the tail
assert to_list(reverse(from_iterable([3, 3, 3]))) == [3, 3, 3]
def test_in_place_and_twice() -> None:
head = from_iterable(range(10))
before = nodes_of(head)
r = reverse(head)
after = nodes_of(r)
assert after == before[::-1] # the same node objects, no new node
assert all(a is b for a, b in zip(after, before[::-1]))
assert to_list(reverse(r)) == list(range(10))
def test_long_list_no_recursion() -> None:
n = 200_000
assert to_list(reverse(from_iterable(range(n)))) == list(range(n - 1, -1, -1))
def test_random_against_slicing() -> None:
rng = random.Random(1027)
for _ in range(600):
a = [rng.randint(-10**18, 10**18) for _ in range(rng.randint(0, 40))]
assert to_list(reverse(from_iterable(a))) == a[::-1]
What the next level needs
- the tests did not run in this build