Reverse a singly linked list, iteratively and recursively.

How to think about it

Reversal is a pointer-discipline question in disguise. You cannot index into a linked list, so the interviewer is watching whether you carry the right state in local variables as you walk and rewire each node without dropping the rest of the chain. The core move is to flip one arrow at a time: a node that pointed forward to next should instead point back to prev. The catch is that overwriting curr.next destroys your only handle on the remaining list — so you save next into a temporary before you flip.

That gives the iterative three-pointer loop: hold prev (the reversed part behind you), curr (the node you are flipping), and a saved nxt (the node ahead). Flip curr.next = prev, then march all three forward. When curr falls off the end, prev is the new head. It uses no extra data structure — pure O(1) space. The recursive form says the same thing differently: reverse the tail first, then hang the current head onto the end of it (head.next.next = head; head.next = None). It reads elegantly but spends O(n) stack frames, so on a very long list it can overflow — prefer the iterative version in production.

A worked example

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

def to_list(head):                 # for printing only
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

# Iterative: O(n) time, O(1) space
def reverse_iter(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next            # save BEFORE you overwrite the pointer
        curr.next = prev           # flip the arrow
        prev = curr                # advance the reversed part
        curr = nxt                 # advance into the rest
    return prev

# Recursive: O(n) time, O(n) call-stack space
def reverse_rec(head):
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head          # tail's next now points back at head
    head.next = None               # head becomes the new tail
    return new_head

head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
print(to_list(reverse_iter(head)))   # five nodes, iterative

head2 = Node(1, Node(2, Node(3)))
print(to_list(reverse_rec(head2)))   # three nodes, recursive

head3 = Node(42)
print(to_list(reverse_iter(head3)))  # single node -> unchanged

print(to_list(reverse_iter(None)))   # empty list -> empty

[5, 4, 3, 2, 1]
[3, 2, 1]
[42]
[]

The first two lines show both methods landing on the same answer — the order is fully reversed. The single-node case returns [42] untouched, and the empty list returns []: both base cases are handled because reverse_iter simply never enters its loop, and the printed lists confirm no node was lost in the rewiring.