Reverse Linked List

Collect + rebuild

The most direct route turns the list into familiar territory. Walk once to collect its values, then build a fresh list by placing each collected value in front of the one you built last.

def reverse_list(head: ListNode | None) -> ListNode | None:
    values: list[int] = []
    current = head
    while current is not None:
        values.append(current.val)
        current = current.next
 
    new_head = None
    for value in values:
        new_head = ListNode(value, new_head)
    return new_head

For 4 → 8 → 15, the rebuild grows as 4, then 8 → 4, then 15 → 8 → 4. It works, but it stores every value and allocates another node for every input node.

Time O(n) — one pass to collect and one to rebuild. Space O(n) for the values and the fresh list.

Iterative pointer reversal

You don't need new nodes. At every step, keep three positions in view:

• current is the node whose link you're about to reverse.
• next_node protects the untouched remainder.
• previous is the head of the part already reversed.

The loop invariant is a fact that remains true after every iteration: previous always heads a correctly reversed prefix, while current heads the untouched suffix.

def reverse_list(head: ListNode | None) -> ListNode | None:
    previous = None
    current = head
 
    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
 
    return previous

Saving next_node before changing current.next is the critical order. Skip that save, and the first reversal cuts off every node you haven't visited yet.

Time O(n) — each node is visited once. Space O(1) — only three node references move, no matter how long the list is.