Reverse a Singly Linked List Recursive in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Reverse on a 3-Node List

What is the printed state of the linked list after recursively reversing it?

DSA Go

package main

import "fmt"

type Node struct {
    val  int
    next *Node
}

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

func printList(head *Node) {
    for head != nil {
        fmt.Printf("%d -> ", head.val)
        head = head.next
    }
    fmt.Println("null")
}

func main() {
    head := &Node{val: 1}
    head.next = &Node{val: 2}
    head.next.next = &Node{val: 3}

    head = reverseRecursive(head)
    printList(head)
}

A null

B 1 -> 2 -> 3 -> null

C 3 -> 2 -> 1 -> null

D 3 -> 1 -> 2 -> null

💡 Hint

Think about how the recursion reverses the links starting from the end.

The recursive function reverses the list by moving to the end and then rewiring the next pointers backward. The final printed list is reversed order.

❓ Predict Output

intermediate

Output of Recursive Reverse on a Single Node List

What is the printed state of the linked list after recursively reversing a single-node list?

DSA Go

package main

import "fmt"

type Node struct {
    val  int
    next *Node
}

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

func printList(head *Node) {
    for head != nil {
        fmt.Printf("%d -> ", head.val)
        head = head.next
    }
    fmt.Println("null")
}

func main() {
    head := &Node{val: 42}

    head = reverseRecursive(head)
    printList(head)
}

A null

B 42 -> 42 -> null

C Error: nil pointer dereference

D 42 -> null

💡 Hint

A single node reversed is itself.

The base case returns the node itself when next is nil, so the list remains unchanged.

🔧 Debug

advanced

Identify the Error in Recursive Reverse Implementation

What error will this recursive reverse function cause when run on a list with multiple nodes?

DSA Go

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

A Runtime panic: nil pointer dereference

B Infinite recursion causing stack overflow

C Compilation error: missing return statement

D Correct reversal of the list

💡 Hint

Check the base case for when head.next is nil.

The base case does not check if head.next is nil, so head.next.next causes nil pointer dereference when head.next is nil.

❓ Predict Output

advanced

Output After Recursive Reverse on a 4-Node List

What is the printed state of the linked list after recursively reversing this 4-node list?

DSA Go

package main

import "fmt"

type Node struct {
    val  int
    next *Node
}

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

func printList(head *Node) {
    for head != nil {
        fmt.Printf("%d -> ", head.val)
        head = head.next
    }
    fmt.Println("null")
}

func main() {
    head := &Node{val: 10}
    head.next = &Node{val: 20}
    head.next.next = &Node{val: 30}
    head.next.next.next = &Node{val: 40}

    head = reverseRecursive(head)
    printList(head)
}

A 10 -> 20 -> 30 -> 40 -> null

B 40 -> 30 -> 20 -> 10 -> null

C 40 -> 20 -> 30 -> 10 -> null

D 30 -> 40 -> 20 -> 10 -> null

💡 Hint

The recursive function reverses the entire list.

The recursive reversal flips the links so the last node becomes the head and the order is reversed.

🧠 Conceptual

expert

Why Does Recursive Reverse Set head.next to nil?

In the recursive reverse function, why do we set 'head.next = nil' after reversing the rest of the list?

A To break the original forward link and avoid cycles in the reversed list

B To mark the end of the list for the base case

C To free memory used by the original next node

D To reset the head pointer to nil for garbage collection

💡 Hint

Think about what happens if we don't break the original link.

Setting 'head.next = nil' breaks the original link so the reversed list does not form a cycle and ends properly.

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