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

Reverse a Singly Linked List Recursive

📖 Scenario: Imagine you have a chain of train cars connected one after another. Sometimes, you want to reverse the order of these cars so the last car becomes the first and the first becomes the last.In programming, a singly linked list is like this chain, where each car (node) points to the next one. Your task is to reverse this chain using a method that calls itself, called recursion.

🎯 Goal: You will build a singly linked list with exact values, then write a recursive method to reverse the list, and finally print the reversed list to see the new order.

📋 What You'll Learn

Create a singly linked list with nodes containing values 10, 20, 30, 40, 50 in that order

Add a recursive method called ReverseRecursive to reverse the linked list

Print the linked list after reversal showing the node values in order

💡 Why This Matters

🌍 Real World

Reversing linked lists is useful in many applications like undo operations, navigation history, and data structure manipulation where order reversal is needed.

💼 Career

Understanding recursive linked list reversal helps in technical interviews and improves problem-solving skills for software development roles involving data structures.

1

Create the singly linked list

Create a class called Node with an int field called Value and a Node field called Next. Then create five nodes with values 10, 20, 30, 40, and 50 linked in that order. Finally, create a variable called head that points to the first node.

DSA C#

// Define Node class and create linked list nodes with values 10, 20, 30, 40, 50 linked
// Assign the first node to variable head
// Your code here

Hint

Start by defining the Node class with Value and Next. Then create each node and link them by setting the Next property.

2

Add a recursive method to reverse the list

Add a method called ReverseRecursive that takes a Node parameter called current and returns a Node. This method should reverse the linked list starting from current using recursion and return the new head of the reversed list.

DSA C#

public class Node
{
    public int Value;
    public Node Next;

    public Node(int value)
    {
        Value = value;
        Next = null;
    }
}

Node head = new Node(10);
head.Next = new Node(20);
head.Next.Next = new Node(30);
head.Next.Next.Next = new Node(40);
head.Next.Next.Next.Next = new Node(50);

// Add the ReverseRecursive method below
// Your code here

Hint

The base case is when current is null or its Next is null. Then return current. Otherwise, call ReverseRecursive on current.Next, then reverse the link by setting current.Next.Next = current and current.Next = null. Finally, return the new head.

3

Call the recursive method to reverse the list

Call the ReverseRecursive method with head as the argument and assign the result back to head to update the head of the reversed list.

DSA C#

public class Node
{
    public int Value;
    public Node Next;

    public Node(int value)
    {
        Value = value;
        Next = null;
    }

    public static Node ReverseRecursive(Node current)
    {
        if (current == null || current.Next == null)
        {
            return current;
        }

        Node newHead = ReverseRecursive(current.Next);
        current.Next.Next = current;
        current.Next = null;

        return newHead;
    }
}

Node head = new Node(10);
head.Next = new Node(20);
head.Next.Next = new Node(30);
head.Next.Next.Next = new Node(40);
head.Next.Next.Next.Next = new Node(50);

// Call ReverseRecursive and update head
// Your code here

Hint

Assign the result of Node.ReverseRecursive(head) back to head to update the list's starting point.

4

Print the reversed linked list

Use a Node variable called current to traverse the linked list starting from head. Print each node's Value followed by " -> " until you reach the end of the list. Finally, print "null" to mark the end.

DSA C#

public class Node
{
    public int Value;
    public Node Next;

    public Node(int value)
    {
        Value = value;
        Next = null;
    }

    public static Node ReverseRecursive(Node current)
    {
        if (current == null || current.Next == null)
        {
            return current;
        }

        Node newHead = ReverseRecursive(current.Next);
        current.Next.Next = current;
        current.Next = null;

        return newHead;
    }
}

Node head = new Node(10);
head.Next = new Node(20);
head.Next.Next = new Node(30);
head.Next.Next.Next = new Node(40);
head.Next.Next.Next.Next = new Node(50);

head = Node.ReverseRecursive(head);

// Print the reversed list
// Your code here

Hint

Use a while loop to go through each node starting from head. Print the Value and an arrow " -> ". After the loop, print "null" to show the list end.

Practice

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

easy

A. Create a new list and copy nodes in reverse order

B. Swap the values of the first and last nodes only

C. Iterate through the list and reverse pointers in a loop

D. Reverse the rest of the list first, then fix the current node's next pointer

Solution

1. Step 1: Understand recursion on linked list

   Recursion works by solving a smaller part first, here reversing from the next node onward.

2. Step 2: Fix current node's pointer after recursion

   After reversing the rest, the current node's next node points back to it, reversing the link.

3. Final Answer:

   Reverse the rest of the list first, then fix the current node's next pointer -> Option D

4. Quick Check:

   Recursive reversal = reverse rest then fix current [OK]

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

Common Mistakes:

• Trying to swap node values instead of pointers
• Not fixing the current node's next pointer after recursion
• Using iteration instead of recursion

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 new Node();

B. if (head.next == null) return null;

C. if (head == null || head.next == null) return head;

D. if (head == null) return head.next;

Solution

1. Step 1: Identify when recursion should stop

   The base case is when the list is empty or has only one node, so no reversal needed.

2. Step 2: Check the correct base case syntax

   Return the head itself if it is null or the last node (head.next == null).

3. Final Answer:

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

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 null when list has one node
• Accessing head.next without checking if head is null
• Creating new nodes unnecessarily

3. What will be the output linked list after running this recursive reverse function on the list 1 -> 2 -> 3 -> null?

Node Reverse(Node head) {
  if (head == null || head.next == null) return head;
  Node newHead = Reverse(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 2 -> 3 -> 1 -> null

D. 3 -> 1 -> 2 -> null

Solution

1. Step 1: Trace recursion calls

   Reverse(1) calls Reverse(2), which calls Reverse(3). Reverse(3) returns node 3 as base case.

2. Step 2: Fix pointers on return

   head.next.next = head reverses link: 3.next = 2, then 2.next = 1, and 1.next = null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

   Recursive reversal output = reversed list [OK]

Hint: Follow recursion bottom-up to see pointer reversal [OK]

Common Mistakes:

• Not setting head.next to null causing cycle
• Confusing node values with pointers
• Returning wrong node as new head

4. Identify the error in this recursive reverse function and choose the fix:

Node Reverse(Node head) {
  if (head == null) return null;
  Node newHead = Reverse(head.next);
  head.next.next = head;
  return newHead;
}

medium

A. Should return head instead of newHead

B. Missing base case for single node; add 'head.next == null' check

C. head.next.next = head causes null pointer; fix by checking head.next

D. No error; code is correct

Solution

1. Step 1: Check base case correctness

   Base case only checks head == null, missing single node case (head.next == null).

2. Step 2: Consequence of missing base case

   Without single node base case, head.next may be null causing head.next.next to throw error.

3. Final Answer:

   Missing base case for single node; add 'head.next == null' check -> Option B

4. Quick Check:

   Base case must handle empty and single node [OK]

Hint: Base case must cover empty and single node to avoid errors [OK]

Common Mistakes:

• Ignoring single node base case
• Not setting head.next = null after reversal
• Returning wrong node as new head

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 == null || head.next == null) return head;
  Node newHead = Reverse(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

// After reversal, print list from newHead

hard

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

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

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

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

Solution

1. Step 1: Trace recursive reversal on given list

   Recursion reverses from last node 40 back to 10, fixing pointers step-by-step.

2. Step 2: Confirm final reversed list order

   After reversal, list order is 40 -> 30 -> 20 -> 10 -> null.

3. Final Answer:

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

4. Quick Check:

   Recursive reversal reverses entire list order [OK]

Hint: Reversal flips list order completely [OK]

Common Mistakes:

• Printing original list instead of reversed
• Forgetting to set head.next = null causing cycle
• Misreading pointer changes as value swaps