Reverse a Singly Linked List Recursive in DSA C - Deep Dive

Overview - Reverse a Singly Linked List Recursive

What is it?

Reverse a singly linked list using recursion. The recursive approach reaches the last node first, then rewires pointers on the way back up the call stack. In C, this involves direct pointer manipulation — the head->next->next = head trick rewires each node's next pointer as the recursion unwinds.

Why it matters

The recursive reversal is a masterclass in thinking backward — trusting the recursive call to handle the subproblem while you handle only the local rewiring. It demonstrates how recursion can elegantly express problems that require processing in reverse order, and deepens understanding of pointer semantics in C.

Where it fits

You need comfort with C pointers, struct node traversal, and basic recursion before tackling this. After mastering it, palindrome linked list checking, k-group reversal, and recursive tree algorithms follow naturally.

Mental Model

Core Idea

Recurse to the last node (new head). On the way back up, make each node's next point backward: head->next->next = head, head->next = NULL.

Think of it like...

Imagine a chain of people each holding the shoulder of the person in front. To reverse: walk to the last person (new leader), then each person grabs the shoulder of the person behind them while releasing the person in front.

Original: 1 → 2 → 3 → 4 → 5 → NULL

Recursion goes to node 5 (base case, new head).

Unwinding:
  At node 4: 4->next->next = 4 (so 5->next = 4). 4->next = NULL.
             4 ← 5
  At node 3: 3->next->next = 3 (so 4->next = 3). 3->next = NULL.
             3 ← 4 ← 5
  At node 2: 2->next->next = 2. 2->next = NULL.
             2 ← 3 ← 4 ← 5
  At node 1: 1->next->next = 1. 1->next = NULL.
             1 ← 2 ← 3 ← 4 ← 5

Result: 5 → 4 → 3 → 2 → 1 → NULL

Build-Up - 6 Steps

1

Foundation

Base Case — Single Node or NULL

Concept: A list with 0 or 1 nodes is already reversed — return head directly.

if (head == NULL || head->next == NULL) return head. This handles two cases: empty list (head == NULL) and single node (head->next == NULL). The single node is the new head after reversal — it's the rightmost node that becomes leftmost. This is also the point where the recursive return value (new_head) is first set.

Result

Base case returns the last node, which becomes the new head for the entire reversed list.

The last node never changes its position in memory — only the pointers around it change. It becomes the new head by being returned up the entire call stack.

2

Foundation

The Recursive Trust

Concept: Trust that reverse(head->next) correctly reverses the rest of the list. Your job: fix only head's local connection.

struct Node* new_head = reverse(head->next). After this call returns, the sublist starting at head->next is fully reversed. The old head->next node now sits at the end of the reversed sublist, and its next pointer is NULL. You only need to: (1) make that tail node point back to head, and (2) set head->next = NULL.

Result

The recursive call handles everything except reconnecting head to the reversed sublist.

This is the key leap in recursive thinking: don't simulate the entire recursion mentally. Trust the function definition — if reverse(rest) works for any list, it works for head->next.

3

Intermediate

The Rewiring Step

🤔Before reading on: after reverse(head->next) returns, where does head->next point? What is head->next->next? Commit to your answer.

Concept: head->next->next = head makes the old second node point back to head. head->next = NULL severs head's old forward link.

After new_head = reverse(head->next): head->next still points to the original second node (now the tail of the reversed sublist). head->next->next is NULL (since that node is now the tail). Set head->next->next = head — this makes the tail point back to head. Set head->next = NULL — this makes head the new tail. Return new_head (the last node of the original list).

Result

head is now correctly appended to the end of the reversed sublist.

head->next->next = head is the single most important line in recursive list reversal. It rewires the connection without losing the new_head reference.

4

Intermediate

Full C Implementation

🤔Before reading on: write the full recursive reverse function from memory. Commit your attempt.

Concept: Three lines of body: recursive call, rewire tail, set NULL, return new_head.

struct Node* reverse(struct Node* head) { if (head == NULL || head->next == NULL) return head; struct Node* new_head = reverse(head->next); head->next->next = head; head->next = NULL; return new_head; } Time: O(n) — one frame per node. Space: O(n) — call stack depth equals list length.

Result

Clean 5-line recursive reversal in C.

new_head is only computed once at the base case and bubbles up unchanged through every recursive frame. Only the local rewiring differs at each level.

5

Advanced

Stack Frame Trace

🤔Before reading on: for list 1→2→3, trace what head->next and head->next->next equal at each unwind step. Commit your trace.

Concept: Each stack frame sees head = its node, head->next = the next node, and does the rewiring.

List: 1→2→3. Calls: reverse(1)→reverse(2)→reverse(3). Base: return node3. Unwind at 2: head=2, head->next=3. 3->next=2, 2->next=NULL. Return node3. Unwind at 1: head=1, head->next=2. 2->next=1, 1->next=NULL. Return node3. Final: 3→2→1→NULL. new_head=node3 throughout.

Result

Complete trace confirms the rewiring pattern is correct at each level.

Each frame executes identically — rewire one connection, set one NULL. The elegance is that no frame knows or needs to know its position in the list.

6

Expert

Stack Overflow Risk and Iterative Alternative

🤔Before reading on: for a list of 100,000 nodes, what is the recursive call stack depth? Is this safe in C? Commit your answer.

Concept: Recursive reversal is O(n) stack space — use iterative for production with large lists.

Recursive reversal has O(n) call stack depth. For n = 100,000+ nodes, this risks stack overflow in C (default stack size ~1-8MB, each frame ~32-64 bytes). Production code uses the iterative approach: three pointers (prev=NULL, curr=head, next=NULL), advance while reversing each link. Time O(n), Space O(1) — no stack growth. The recursive version is pedagogically valuable but iterative is production-safe for large lists.

Result

Recursive is elegant and interview-appropriate; iterative is production-safe.

Interviewers often ask for both. Recursive first (shows understanding), then iterative (shows production awareness). Always mention the stack overflow risk for large lists.

Under the Hood

The recursion unwinds from the last node back to the first. At each unwind step, exactly two pointer operations occur: head->next->next = head (backward link) and head->next = NULL (forward link severed). The new_head reference (originally the last node) is passed back unchanged through all frames. After all frames return, new_head is the head of the fully reversed list.

Why designed this way?

Linked list reversal naturally maps to recursion because the reversal of a list is: reverse the tail, then append the head. This decomposition is the recursive structure. The rewiring step implements 'append head' after 'reverse tail' has been done by the recursive call.

Call stack for 1→2→3:

reverse(1) ─── calls ──► reverse(2) ─── calls ──► reverse(3)
                                                     returns node3
              ◄─ node3 ── reverse(2) rewires: 3→2, 2→NULL
                          returns node3
◄─ node3 ─── reverse(1) rewires: 2→1, 1→NULL
             returns node3

Final: node3 is new head. List is 3→2→1→NULL.

Myth Busters - 3 Common Misconceptions

Quick: after reverse(head->next) returns, does head->next change? Commit yes or no.

Common Belief: After the recursive call, head->next points to the new head.

Reality: head->next still points to the original second node — unchanged. The recursive call reverses the sublist internally but doesn't change head->next. You must manually rewire using head->next->next = head.

Why it matters: Many students write new_head->next = head thinking the recursive call already set up the connection. It doesn't — you must explicitly do head->next->next = head.

Quick: is head->next = NULL necessary? What happens if you omit it? Commit your answer.

Common Belief: head->next = NULL is optional cleanup.

Reality: head->next = NULL is mandatory. Without it, the original head node still points forward to the second node, creating a cycle: 1↔2 (both point to each other). The list becomes circular and traversal loops forever.

Why it matters: Omitting head->next = NULL is the most common bug in recursive reversal — it creates a cycle that causes infinite loops during traversal.

Quick: what does the recursive call return when the list has only one node? Commit your answer.

Common Belief: The recursive call returns NULL for a single node.

Reality: The base case (head->next == NULL) returns head — the single node itself, not NULL. It returns the node that will become the new head of the entire reversed list.

Why it matters: Confusing the base case return value leads to incorrect new_head handling. The single last node is a valid non-NULL pointer that becomes the new head.

Expert Zone

1

In C, there is no garbage collector. After reversal, the original head is now the tail with next=NULL. No memory leak occurs — all nodes remain in the same memory locations, only pointers changed.

2

The recursive approach requires O(n) stack frames. For embedded C systems with limited stack, the iterative approach (prev/curr/next) is mandatory.

3

If you need to reverse in groups of k, the recursive structure generalizes: reverse k nodes locally, recurse on the rest, connect. This is the k-group reversal problem.

When NOT to use

For very long lists (>10,000 nodes) in production C code, use the iterative approach to avoid stack overflow. For competitive programming where list length is bounded (typically ≤1000), recursive is clean and acceptable.

Production Patterns

Recursive list reversal appears in: palindrome linked list checking (reverse second half), k-group reversal, and reorder list problems. The pattern of 'trust the recursive call, fix local connection' appears in tree mirroring, flatten linked list, and merge sort.

Connections

Reverse a Singly Linked List Iterative

Same result, different mechanism. Iterative uses three pointers (prev, curr, next) with O(1) space. Recursive uses the call stack implicitly as O(n) space.

Both implementations do exactly n pointer swaps. The recursive version distributes them across stack frames; the iterative version does them in one loop.

Palindrome Linked List Check

Palindrome check reverses the second half of the list using this exact function, then compares with the first half.

Mastering recursive reversal directly enables palindrome linked list — one of the most common linked list interview questions.

Common Pitfalls

#1 Forgetting head->next = NULL, creating a cycle.

Wrong approach:

struct Node* new_head = reverse(head->next);
head->next->next = head;
// Missing: head->next = NULL
return new_head;

Correct approach:

struct Node* new_head = reverse(head->next);
head->next->next = head;
head->next = NULL; // Critical: severs forward link
return new_head;

Root cause:

Without head->next = NULL, node 1 (new tail) still points to node 2, and node 2 points back to node 1 — a cycle. Any traversal loops forever.

#2 Saving head->next before the recursive call (not needed).

Wrong approach:

struct Node* rest = head->next; // Unnecessary
struct Node* new_head = reverse(rest);
rest->next = head; // Works but verbose
head->next = NULL;
return new_head;

Correct approach:

struct Node* new_head = reverse(head->next);
head->next->next = head; // head->next unchanged after recursive call
head->next = NULL;
return new_head;

Root cause:

head->next doesn't change during the recursive call — no need to save it. Using head->next->next directly is cleaner and more idiomatic.

Key Takeaways

Base case: NULL or single node → return head (the future new tail becomes the first return value).

Recursive call handles reversing the rest. Your job: rewire head's connection.

head->next->next = head adds head to the end of the reversed sublist.

head->next = NULL is mandatory — without it, a cycle forms and traversal loops forever.

Return new_head unchanged through all frames — it's set once at the base case and passed back unmodified.

Practice

1. What is the main idea behind reversing a singly linked list using recursion?

easy

A. Use a stack to store nodes and pop them in reverse order

B. Reverse the rest of the list and then fix the first node's next pointer

C. Swap the data values of nodes from start to end

D. Iterate through the list and reverse pointers one by one

Solution

1. Step 1: Understand recursion on linked list

   Recursion reverses the list from the second node onward first.

2. Step 2: Fix the first node's next pointer

   After recursion returns, the first node's next pointer is set to null and the previous node points back to it.

3. Final Answer:

   Reverse the rest of the list and then fix the first node's next pointer -> Option B

4. Quick Check:

   Recursive reversal = Reverse rest + fix first [OK]

Hint: Think: reverse smaller list first, then fix current node [OK]

Common Mistakes:

• Trying to swap node data instead of pointers
• Not setting the first node's next to null
• Confusing iterative and recursive methods

2. Which of the following is the correct base case for a recursive function that reverses a singly linked list?

easy

A. if (head == NULL) return NULL;

B. if (head->next == NULL) return head;

C. if (head == NULL || head->next == NULL) return head;

D. if (head->next == NULL) head = NULL;

Solution

1. Step 1: Identify base cases for recursion

   Base case must handle empty list and single node list to stop recursion.

2. Step 2: Choose correct condition

   Condition 'head == NULL || head->next == NULL' covers both empty and single node cases.

3. Final Answer:

   if (head == NULL || head->next == NULL) return head; -> Option C

4. Quick Check:

   Base case = empty or single node [OK]

Hint: Base case stops recursion on empty or single node [OK]

Common Mistakes:

• Returning NULL for single node list
• Not handling empty list as base case
• Incorrectly modifying head in base case

3. What will be the output linked list after reversing recursively the list: 1 -> 2 -> 3 -> NULL?

medium

A. 3 -> 1 -> 2 -> NULL

B. 1 -> 2 -> 3 -> NULL

C. 2 -> 3 -> 1 -> NULL

D. 3 -> 2 -> 1 -> NULL

Solution

1. Step 1: Trace recursive reversal

   Recursion reverses from last node back: 3 becomes new head, 2 points to 1, 1 points to NULL.

2. Step 2: Confirm final list order

   Final reversed list is 3 -> 2 -> 1 -> NULL.

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option D

4. Quick Check:

   Reverse(1->2->3) = 3->2->1 [OK]

Hint: Last node becomes new head after recursion [OK]

Common Mistakes:

• Assuming original order remains
• Mixing node values instead of pointers
• Forgetting to set last node's next to NULL

4. Identify the error in this recursive reverse function snippet:

Node* reverse(Node* head) {
  if (head == NULL || head->next == NULL) return head;
  Node* rest = reverse(head->next);
  head->next->next = head;
  head->next = head;
  return rest;
}

medium

A. head->next is set to head instead of NULL causing a cycle

B. Missing base case for empty list

C. Incorrect return value; should return head

D. No recursive call made

Solution

1. Step 1: Analyze pointer assignments

   head->next->next = head correctly points next node back to current node.

2. Step 2: Identify incorrect pointer reset

   head->next = head wrongly points current node's next to itself, causing a cycle instead of NULL.

3. Final Answer:

   head->next is set to head instead of NULL causing a cycle -> Option A

4. Quick Check:

   head->next must be NULL, not head [OK]

Hint: Set head->next to NULL to avoid cycles [OK]

Common Mistakes:

• Setting head->next to head causing infinite loop
• Forgetting to return the new head
• Not handling base case properly

5. Given a singly linked list with nodes containing values 10 -> 20 -> 30 -> 40 -> NULL, what will be the printed output after applying this recursive reverse function?

Node* reverse(Node* head) {
  if (!head || !head->next) return head;
  Node* rest = reverse(head->next);
  head->next->next = head;
  head->next = NULL;
  return rest;
}

void printList(Node* head) {
  while (head) {
    printf("%d -> ", head->data);
    head = head->next;
  }
  printf("NULL\n");
}

int main() {
  // List creation omitted for brevity
  Node* reversed = reverse(head);
  printList(reversed);
}

hard

A. 40 -> 30 -> 20 -> 10 -> NULL

B. 10 -> 20 -> 30 -> 40 -> NULL

C. NULL

D. 40 -> 20 -> 30 -> 10 -> NULL

Solution

1. Step 1: Trace recursive reversal on list 10->20->30->40

   Recursion reverses from last node: 40 becomes new head, pointers reversed stepwise.

2. Step 2: Confirm print output

   Print function outputs nodes in order: 40 -> 30 -> 20 -> 10 -> NULL.

3. Final Answer:

   40 -> 30 -> 20 -> 10 -> NULL -> Option A

4. Quick Check:

   Reverse(10->20->30->40) = 40->30->20->10 [OK]

Hint: Last node becomes head; print from new head [OK]

Common Mistakes:

• Assuming original order remains after reverse
• Forgetting to set last node's next to NULL
• Confusing print output with input list