Reversing a Linked List: Iterative and Recursive

Reversing a linked list means flipping every next pointer so the last node becomes the head and the head becomes the last node. It is the single most common linked-list interview question because it tests whether you can rewire pointers without losing the rest of the chain. There are two canonical approaches — iterative (three pointers) and recursive — and both run in O(n) time. We work with a singly linked list.

The iterative method (three pointers)

Walk the list once, flipping each node’s link to point at the node behind it. You need three references: prev (the new successor), cur (the node being flipped), and a saved next so you don’t lose the rest of the list.

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != nullptr) {
        Node* next = cur->next; // save the rest
        cur->next = prev;       // flip the link
        prev = cur;             // advance prev
        cur = next;             // advance cur
    }
    return prev;                // prev is the new head
}

Node reverse(Node head) {
    Node prev = null;
    Node cur = head;
    while (cur != null) {
        Node next = cur.next;   // save the rest
        cur.next = prev;        // flip the link
        prev = cur;             // advance prev
        cur = next;             // advance cur
    }
    return prev;                // prev is the new head
}

function reverse(head) {
  let prev = null;
  let cur = head;
  while (cur !== null) {
    const next = cur.next;  // save the rest
    cur.next = prev;        // flip the link
    prev = cur;             // advance prev
    cur = next;             // advance cur
  }
  return prev;              // prev is the new head
}

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next   # save the rest
        cur.next = prev  # flip the link
        prev = cur       # advance prev
        cur = nxt        # advance cur
    return prev          # prev is the new head

Walking through it

Starting from 1 -> 2 -> 3 -> None:

prev=None  cur=1     : save 2, 1->None, prev=1, cur=2
prev=1     cur=2     : save 3, 2->1,    prev=2, cur=3
prev=2     cur=3     : save None, 3->2, prev=3, cur=None
loop ends, return prev=3  =>  3 -> 2 -> 1 -> None

This is O(n) time and O(1) extra space — the gold standard.

The recursive method

Reverse everything after the head, then flip the link between the head and its old next. The recursion bottoms out at the last node, which becomes the new head and bubbles back up unchanged.

Node* reverse(Node* head) {
    if (head == nullptr || head->next == nullptr) return head;
    Node* newHead = reverse(head->next);
    head->next->next = head;  // make the next node point back
    head->next = nullptr;     // sever the old forward link
    return newHead;
}

Node reverse(Node head) {
    if (head == null || head.next == null) return head;
    Node newHead = reverse(head.next);
    head.next.next = head;    // make the next node point back
    head.next = null;         // sever the old forward link
    return newHead;
}

function reverse(head) {
  if (head === null || head.next === null) return head;
  const newHead = reverse(head.next);
  head.next.next = head;    // make the next node point back
  head.next = null;         // sever the old forward link
  return newHead;
}

def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next)
    head.next.next = head    # make the next node point back
    head.next = None         # sever the old forward link
    return new_head

The recursive version is O(n) time but O(n) space because of the call stack — one frame per node.

Iterative vs recursive

Aspect	Iterative	Recursive
Time	O(n)	O(n)
Extra space	O(1)	O(n) call stack
Risk	none	stack overflow on huge lists
Readability	very clear	elegant but subtle

For beginners: The whole game is don’t lose the rest of the list. The moment you overwrite cur->next, the tail is gone unless you saved it first. That single saved pointer is why the iterative loop needs three variables, not two.

Pitfall: In the recursive version, forgetting head->next = nullptr leaves the old head pointing forward and being pointed back to — creating a two-node cycle. The original head must become the new tail with a null link.

Where reversal shows up

Reversal is a building block: reversing a sublist (between positions m and n), checking whether a list is a palindrome (reverse the second half and compare), and reversing in k-groups all reuse this three-pointer flip. Mastering it makes those harder problems routine.

Next: the fast & slow pointers technique for cycle detection and finding the middle, then the exercises.