Reverse a Singly Linked List Recursive in DSA Go - Execution Trace

Concept Flow - Reverse a Singly Linked List Recursive

Start with head node

↓

Check if head is nil or head.next is nil?

Yes→Return head as new head

No↓

Recursive call: reverseList(head.next)

↓

Reverse link: head.next.next = head

↓

Set head.next = nil

↓

Return new head from recursion

↓

End with reversed list head

The function recursively goes to the last node, then reverses the links on the way back, setting each next pointer backwards until the entire list is reversed.

Execution Sample

DSA Go

func reverseList(head *Node) *Node {
  if head == nil || head.next == nil {
    return head
  }
  newHead := reverseList(head.next)
  head.next.next = head
  head.next = nil
  return newHead
}

This code reverses a singly linked list by recursively reversing the rest of the list and then fixing the current node's next pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Call reverseList with head=1	1 -> 2 -> 3 -> 4 -> nil	No change	1 -> 2 -> 3 -> 4 -> nil
2	Call reverseList with head=2	1 -> 2 -> 3 -> 4 -> nil	No change	1 -> 2 -> 3 -> 4 -> nil
3	Call reverseList with head=3	1 -> 2 -> 3 -> 4 -> nil	No change	1 -> 2 -> 3 -> 4 -> nil
4	Call reverseList with head=4 (base case)	1 -> 2 -> 3 -> 4 -> nil	No change	1 -> 2 -> 3 -> 4 -> nil
5	Return head=4 as newHead	1 -> 2 -> 3 -> 4 -> nil	No change	1 -> 2 -> 3 -> 4 -> nil
6	Reverse link: 3.next.next = 3	1 -> 2 -> 3 -> 4 -> nil	4.next = 3	1 -> 2 -> 3 <- 4 nil
7	Set 3.next = nil	1 -> 2 -> 3 <- 4 nil	3.next = nil	1 -> 2 -> 3 nil 4
8	Return newHead=4	1 -> 2 -> 3 nil 4	No change	1 -> 2 -> 3 nil 4
9	Reverse link: 2.next.next = 2	1 -> 2 -> 3 nil 4	3.next = 2	1 -> 2 <- 3 nil 4
10	Set 2.next = nil	1 -> 2 <- 3 nil 4	2.next = nil	1 -> 2 nil 3 nil 4
11	Return newHead=4	1 -> 2 nil 3 nil 4	No change	1 -> 2 nil 3 nil 4
12	Reverse link: 1.next.next = 1	1 -> 2 nil 3 nil 4	2.next = 1	1 <- 2 nil 3 nil 4
13	Set 1.next = nil	1 <- 2 nil 3 nil 4	1.next = nil	1 nil 2 nil 3 nil 4
14	Return newHead=4 (final reversed list head)	1 nil 2 nil 3 nil 4	No change	4 -> 3 -> 2 -> 1 -> nil

💡 Recursion ends when head.next is nil (step 4), then returns new head and reverses links on unwind.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	After Step 13	Final
head	1	4	3	2	1	1
newHead	nil	4	4	4	4	4
head.next	2	nil	nil	nil	nil	nil
List State	1->2->3->4->nil	1->2->3->4->nil	1->2->3 nil 4	1->2 nil 3 nil 4	1 nil 2 nil 3 nil 4	4->3->2->1->nil

Key Moments - 3 Insights

Why do we set head.next = nil after reversing the link?

Because after reversing, the current node's next pointer still points forward, causing a cycle. Setting head.next = nil breaks the old forward link, as shown in steps 7, 10, and 13 in the execution_table.

Why does the recursion stop when head.next is nil?

Because that means we reached the last node, which becomes the new head of the reversed list. This is the base case at step 4 where recursion stops and returns the new head.

How does the list visually change during recursion unwind?

On each return, the next node's next pointer is set back to the current node, reversing the link. The visual state changes from forward arrows to backward arrows as seen from step 6 onwards.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what pointer change happens?

A 4.next points to 3

B 3.next points to 4

C 3.next is set to nil

D 1.next points to 2

💡 Hint

Check the 'Pointer Changes' column at step 6 in execution_table.

At which step does the recursion base case occur?

A Step 1

B Step 4

C Step 7

D Step 14

💡 Hint

Look for the step where head.next is nil and recursion stops in execution_table.

If we forget to set head.next = nil, what would happen to the list?

A The list would be correctly reversed

B The list would be empty

C The list would have a cycle causing infinite loop

D The list would remain unchanged

💡 Hint

Refer to key_moments explanation about setting head.next = nil to avoid cycles.

Concept Snapshot

Reverse a singly linked list recursively:
- Base case: if head is nil or head.next is nil, return head
- Recursively reverse rest of list
- Set head.next.next = head to reverse link
- Set head.next = nil to break old link
- Return new head from recursion
This reverses the list by fixing links on recursion unwind.

Full Transcript

This visualization shows how to reverse a singly linked list using recursion. The function calls itself until it reaches the last node, which becomes the new head. Then, as recursion returns, it reverses the links by pointing the next node back to the current node and breaking the old forward link by setting head.next to nil. The execution table traces each step, showing how the nodes and pointers change. Key moments clarify why we set head.next to nil and why recursion stops at the last node. The visual quiz tests understanding of pointer changes, base case, and consequences of missing steps.

Practice

1. What does the recursive function to reverse a singly linked list do at each step?

easy

A. It reverses the rest of the list and then attaches the current node at the end.

B. It swaps the first two nodes and stops.

C. It deletes the current node and moves to the next.

D. It creates a new list and copies nodes in reverse order.

Solution

1. Step 1: Understand recursion on linked list

   The function calls itself on the next node until it reaches the last node.

2. Step 2: Attach current node after reversing rest

   After recursion returns, it sets the next node's next pointer to current node, reversing the link.

3. Final Answer:

   It reverses the rest of the list and then attaches the current node at the end. -> Option A

4. Quick Check:

   Recursive reversal = attach current after reversed rest [OK]

Hint: Think: reverse rest first, then fix current link [OK]

Common Mistakes:

• Stopping recursion too early
• Not changing next pointers correctly
• Trying to reverse by swapping values

2. Which of the following is the correct base case for a recursive function reversing a singly linked list in Go?

easy

A. if head == nil { return nil }

B. if head == nil || head.Next == nil { return head }

C. if head.Next == nil { return nil }

D. if head == nil && head.Next == nil { return nil }

Solution

1. Step 1: Identify base case for recursion

   The recursion stops when the list is empty or has one node, so head is nil or head.Next is nil.

2. Step 2: Return head in base case

   Return the head node itself because a single node or empty list is already reversed.

3. Final Answer:

   if head == nil || head.Next == nil { return head } -> Option B

4. Quick Check:

   Base case = empty or single node returns head [OK]

Hint: Base case: empty or single node returns itself [OK]

Common Mistakes:

• Returning nil for single node
• Using && instead of || in condition
• Missing base case causing infinite recursion

3. What is the output linked list after running this recursive reverse function on the list 1 -> 2 -> 3 -> nil?

func reverse(head *Node) *Node {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

medium

A. nil

B. 1 -> 2 -> 3 -> nil

C. 2 -> 3 -> 1 -> nil

D. 3 -> 2 -> 1 -> nil

Solution

1. Step 1: Trace recursion calls

   Calls reverse on 2 -> 3 -> nil, then on 3 -> nil (base case returns 3).

2. Step 2: Reverse links on return

   Sets 3.Next to 2, 2.Next to 1, and 1.Next to nil, reversing the list.

3. Final Answer:

   3 -> 2 -> 1 -> nil -> Option D

4. Quick Check:

   Reversed list = 3->2->1 [OK]

Hint: Follow recursion bottom-up to see reversed links [OK]

Common Mistakes:

• Not setting head.Next to nil causing cycle
• Returning wrong node as new head
• Confusing order of pointer assignments

4. Identify the bug in this recursive reverse function for a singly linked list:

func reverse(head *Node) *Node {
    if head == nil {
        return nil
    }
    newHead := reverse(head.Next)
    head.Next.Next = head
    return newHead
}

medium

A. head.Next.Next should be head.Next

B. Incorrect return type

C. Missing base case for single node causing nil pointer dereference

D. No bug, code is correct

Solution

1. Step 1: Check base case correctness

   Base case only checks if head is nil, but not if head.Next is nil, causing head.Next.Next to panic if head.Next is nil.

2. Step 2: Identify nil pointer dereference

   When head.Next is nil, head.Next.Next causes runtime error because head.Next is nil.

3. Final Answer:

   Missing base case for single node causing nil pointer dereference -> Option C

4. Quick Check:

   Base case must handle single node to avoid nil panic [OK]

Hint: Always check base case for nil and single node [OK]

Common Mistakes:

• Ignoring single node base case
• Assuming head.Next is never nil
• Not setting head.Next to nil after reversal

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

func reverse(head *Node) *Node {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverse(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

Choose the correct final linked list.

hard

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

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

C. 40 -> 10 -> 20 -> 30 -> nil

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

Solution

1. Step 1: Recursively reverse from tail

   Recursion reaches node with value 40 (base case), then reverses links back up.

2. Step 2: Re-link nodes in reverse order

   Each node's next node points back to itself, and original head's next is set to nil.

3. Final Answer:

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

4. Quick Check:

   Reversed list = 40->30->20->10 [OK]

Hint: Reverse order means last node becomes new head [OK]

Common Mistakes:

• Forgetting to set head.Next to nil
• Returning old head instead of new head
• Misordering nodes after reversal