Reverse a Singly Linked List Recursive in DSA Go - Build from Scratch

Reverse a Singly Linked List Recursive

📖 Scenario: You are working on a simple program that manages a list of tasks. The tasks are stored in a singly linked list, where each task points to the next one. Sometimes, you want to see the tasks in reverse order.

🎯 Goal: Build a Go program that creates a singly linked list of tasks, then reverses the list using a recursive function, and finally prints the reversed list.

📋 What You'll Learn

Create a singly linked list with exactly three nodes containing the strings "Task1", "Task2", and "Task3" in that order.

Add a variable called head that points to the first node of the list.

Write a recursive function called reverseList that takes a pointer to a node and returns the pointer to the reversed list's head.

Use the reverseList function to reverse the list starting from head.

Print the reversed list nodes in order separated by arrows like: Task3 -> Task2 -> Task1 -> nil

💡 Why This Matters

🌍 Real World

Linked lists are used in many software systems to manage ordered data where insertions and deletions happen frequently, such as task schedulers or undo history.

💼 Career

Understanding linked lists and recursion is important for software developers, especially when working with low-level data structures or preparing for technical interviews.

1

Create the singly linked list nodes

Create a struct type called Node with a field value of type string and a field next of type *Node. Then create three variables node1, node2, and node3 of type Node with values "Task1", "Task2", and "Task3" respectively. Link node1.next to node2 and node2.next to node3. Set node3.next to nil.

DSA Go

package main

import "fmt"

type Node struct {
    value string
    next  *Node
}

func main() {
    // Create node1, node2, node3 and link them
    // Your code here
}

Hint

Define the Node struct first. Then create three nodes with the given values. Link them by setting the next field to point to the next node.

2

Add the head pointer to the first node

Inside main, create a variable called head of type *Node and set it to point to node1.

DSA Go

package main

import "fmt"

type Node struct {
    value string
    next  *Node
}

func main() {
    node1 := Node{value: "Task1"}
    node2 := Node{value: "Task2"}
    node3 := Node{value: "Task3"}

    node1.next = &node2
    node2.next = &node3
    node3.next = nil

    // Create head pointer to node1
    // Your code here
}

Hint

Use head := &node1 to point to the first node.

3

Write the recursive reverse function

Write a recursive function called reverseList that takes a parameter node of type *Node and returns *Node. The function should reverse the linked list starting from node and return the new head of the reversed list. Use the base case when node is nil or node.next is nil. Otherwise, recursively reverse the rest of the list and adjust pointers to reverse the current node.

DSA Go

package main

import "fmt"

type Node struct {
    value string
    next  *Node
}

func reverseList(node *Node) *Node {
    // Your code here
}

func main() {
    node1 := Node{value: "Task1"}
    node2 := Node{value: "Task2"}
    node3 := Node{value: "Task3"}

    node1.next = &node2
    node2.next = &node3
    node3.next = nil

    head := &node1

}

Hint

Use recursion to reverse the list. The base case is when the node is nil or its next is nil. Then reverse the rest and fix the pointers.

4

Reverse the list and print the result

In main, call reverseList with head and assign the result back to head. Then use a for loop with a variable current starting at head to print each node's value followed by " -> ". After the loop, print "nil" to mark the end of the list.

DSA Go

package main

import "fmt"

type Node struct {
    value string
    next  *Node
}

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

func main() {
    node1 := Node{value: "Task1"}
    node2 := Node{value: "Task2"}
    node3 := Node{value: "Task3"}

    node1.next = &node2
    node2.next = &node3
    node3.next = nil

    head := &node1

    // Reverse the list and print it
    // Your code here
}

Hint

Call head = reverseList(head). Then loop through the list starting at head and print each value followed by " -> ". Finally, print "nil".

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