Reverse Linked List Solution

Problem

Given a singly linked list, reverse the direction of all its pointers so the last node becomes the head and the original head becomes the tail.

→

→∅

[1,2,3,4,5]

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: Every pointer is flipped, so the list now runs from 5 back to 1.

Intuition

The difficulty is that you can only follow pointers forward — once you redirect a node's next pointer to face backward, you'd lose your path to the rest of the list unless you saved it first. The iterative solution carries three positions at once: where you've been (prev), where you are (current), and where you're going (next_node), allowing you to flip current without losing the tail.

Approach 1 — Iterative

Walk the list one node at a time, flipping each next pointer to face the previous node before advancing.

Initialize prev = None and current = head.
While current is not null, save next_node = current.next before overwriting anything.
Redirect current.next = prev to flip the pointer backward.
Advance prev to current and current to next_node.
Return prev — it holds the new head once current falls off the end.

1def reverseList(head):
2    prev = None
3    current = head
4    while current:
5        next_node = current.next  # must save before overwriting
6        current.next = prev       # flip the pointer backward
7        prev = current
8        current = next_node
9    return prev

Time: O(n) — each node is visited exactly once.
Space: O(1) — only three pointer variables regardless of list length.

Approach 2 — Recursive

Recurse all the way to the tail, then redirect each node's former successor back at it on the way back up.

Base case: if head is null or head.next is null, return head (single node is already reversed).
Recurse into head.next to reverse the rest of the list; capture the returned new head.
head.next.next = head makes the node that was after head point back at head.
head.next = None cuts head's forward link to prevent a cycle.
Return new_head unchanged through every recursive frame.

1def reverseList(head):
2    if not head or not head.next:
3        return head
4    new_head = reverseList(head.next)
5    head.next.next = head  # redirect former successor back at head
6    head.next = None       # cut the forward link to prevent a cycle
7    return new_head

Time: O(n) — one recursive call per node.
Space: O(n) — one stack frame per node deep in the call stack.

Complexity Summary

Approach	Time	Space	When to use
Iterative	O(n)	O(1)	Default choice; constant space is safer for long lists
Recursive	O(n)	O(n)	When recursive style is preferred and list length is bounded

Common Mistakes

Not saving next_node before redirecting — setting current.next = prev immediately orphans the rest of the list; you must capture current.next in a temporary variable first.
Returning current instead of prev — current is None when the loop exits; prev holds the new head and is the correct return value.
Forgetting head.next = None in the recursive version — without it, the original head still points forward and creates a cycle in the reversed list.
Initializing prev = head instead of None — when the first node is processed, current.next = prev makes it point at itself, corrupting the list.
Using while current.next instead of while current — the loop stops one node too early, leaving the last node unflipped and disconnected from the reversed portion.

Reverse Linked List — Solution