Reverse a Singly Linked List Recursive in DSA C#

Mental Model

We flip the direction of each link in the list by going to the end first, then reversing links on the way back.

Analogy: Imagine unrolling a chain from the last link back to the first, flipping each link's direction as you go back.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Reverse the list so it becomes 3 -> 2 -> 1 -> null using recursion

Step 1: call reverse on node 1, which calls reverse on node 2

head -> 1 -> 2 -> 3 -> null ↑ (recursion going deeper)

Why: We need to reach the last node before reversing links

Step 2: call reverse on node 2, which calls reverse on node 3

head -> 1 -> 2 -> 3 -> null ↑ (recursion going deeper)

Why: Keep going deeper until last node to start reversal

Step 3: reverse called on node 3 returns node 3 as new head

head -> 1 -> 2 -> 3 -> null ↑ (start reversing links)

Why: Last node becomes new head of reversed list

Step 4: node 2's next (3) points back to node 2, node 2's next set to null

head -> 1 -> 2 -> null
3 -> 2 -> null ↑ (partial reversal)

Why: Flip link between 2 and 3 to reverse direction

Step 5: node 1's next (2) points back to node 1, node 1's next set to null

head -> 1 -> null
2 -> 1 -> null
3 -> 2 -> 1 -> null ↑ (full reversal)

Why: Flip link between 1 and 2 to complete reversal

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA C#

using System;

public class Node
{
    public int val;
    public Node next;
    public Node(int val = 0, Node next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class LinkedList
{
    public Node head;

    public LinkedList(int[] values)
    {
        if (values.Length == 0) return;
        head = new Node(values[0]);
        Node current = head;
        for (int i = 1; i < values.Length; i++)
        {
            current.next = new Node(values[i]);
            current = current.next;
        }
    }

    public Node ReverseRecursive(Node node)
    {
        if (node == null || node.next == null) return node; // base case: last node or empty

        Node newHead = ReverseRecursive(node.next); // recurse to end

        node.next.next = node; // flip link direction
        node.next = null; // set current node next to null

        return newHead; // return new head up the call stack
    }

    public void PrintList()
    {
        Node current = head;
        while (current != null)
        {
            Console.Write(current.val);
            if (current.next != null) Console.Write(" -> ");
            current = current.next;
        }
        Console.WriteLine(" -> null");
    }
}

public class Program
{
    public static void Main()
    {
        LinkedList list = new LinkedList(new int[] {1, 2, 3});
        list.PrintList();
        list.head = list.ReverseRecursive(list.head);
        list.PrintList();
    }
}

if (node == null || node.next == null) return node; // base case: last node or empty

stop recursion at last node or empty list

Node newHead = ReverseRecursive(node.next); // recurse to end

go deeper to reach last node first

node.next.next = node; // flip link direction

reverse the pointer of next node back to current

node.next = null; // set current node next to null

break old forward link to avoid cycle

return newHead; // return new head up the call stack

pass new head back through recursion

Output

1 -> 2 -> 3 -> null

3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once during recursion

Space: O(n) due to recursion call stack for n nodes

vs Alternative: Iterative reversal uses O(1) space but recursion is simpler to write and understand

Edge Cases

empty list

returns null immediately without error

DSA C#

if (node == null || node.next == null) return node; // base case: last node or empty

single node list

returns the single node as new head without changes

DSA C#

if (node == null || node.next == null) return node; // base case: last node or empty

When to Use This Pattern

When you see a problem asking to reverse a linked list and recursion is allowed, use recursive reversal to simplify pointer flipping by going to the end first.

Common Mistakes

Mistake: Not setting node.next to null after reversing the pointer, causing cycles
Fix: Always set node.next = null after flipping the pointer to break old forward link

Mistake: Returning node instead of newHead, losing the new head reference
Fix: Return newHead from recursion to keep track of reversed list head

Summary

Reverses a singly linked list by recursively flipping pointers from the end back to the start.

Use when you want a clean, elegant way to reverse a list using recursion.

The key insight is to reverse links on the way back from the deepest recursive call, not going down.

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