Reverse Linked List

Reverse all links in a singly linked list.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Reverse Linked List: Preserve the unreversed suffix before redirecting each current.next, then advance the previous/current boundary one node.

Input and goalReverse all links in a singly linked list.

Initialize the two list regionsFor 1->2->3->4->null, previous = null and head/current = 1. The whole list is still the unreversed suffix.

1current→2→3→4

previousnullactualLinks1->2, 2->3, 3->4, 4->null

Recognize it

Use it when a forward-only chain must reverse direction in constant extra space and changing current.next would otherwise destroy access to the unprocessed suffix.

Keep true

Before each iteration, previous heads a fully reversed prefix, head heads the untouched forward suffix, and together those disjoint regions contain every original node exactly once.

Reuse it

Before mutating the only route to remaining work, save that route; then rewire and advance the boundary. This applies to list splicing, segment reversal, and in-place pointer transformations.

Pattern: Previous, current, and next pointers.

Simple idea: Save the next node. Point the current node backward. Move both working pointers forward.

def reverse_list(head: ListNode | None) -> ListNode | None:
   previous = None

   while head:
      next_node = head.next
      head.next = previous
      previous = head
      head = next_node

   return previous

Cost: $O(n)$ time and $O(1)$ space.

The platform supplies ListNode with val and next; this snippet assumes that definition.