Reverse a Singly Linked List Recursive in DSA Java

Mental Model

We flip the direction of the links between nodes by going to the end first, then reversing links on the way back.

Analogy: Imagine a line of dominoes standing. Instead of pushing from the front, you go to the last domino and then push backward, flipping each domino's direction one by one.

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

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 3, base case reached, return node 3

head -> 1 -> 2 -> 3 -> null ↑ (at last node)

Why: Last node becomes new head of reversed list

Step 3: reverse link: node 3's next (null) stays, node 2's next points back to node 2

head -> 1 -> 2 ← 3 -> null (node 3 points back to 2)

Why: Flip link between node 2 and 3

Step 4: reverse link: node 2's next points back to node 1

head -> 1 ← 2 ← 3 -> null (node 2 points back to 1)

Why: Flip link between node 1 and 2

Step 5: set node 1's next to null to end reversed list

null ← 1 ← 2 ← 3 (new head is node 3)

Why: Old head becomes tail, so next must be null

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA Java

public class LinkedList {
    static class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; this.next = null; }
    }

    // Recursive reverse function
    public static Node reverseRecursive(Node head) {
        if (head == null || head.next == null) {
            return head; // base case: empty or single node
        }
        Node newHead = reverseRecursive(head.next); // reverse rest
        head.next.next = head; // flip link
        head.next = null; // old head becomes tail
        return newHead; // new head of reversed list
    }

    // Helper to print list
    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        System.out.print("Original list: ");
        printList(head);

        Node reversed = reverseRecursive(head);

        System.out.print("Reversed list: ");
        printList(reversed);
    }
}

if (head == null || head.next == null) {

base case: stop recursion at empty or single node

Node newHead = reverseRecursive(head.next);

recursively reverse the rest of the list

head.next.next = head;

flip the link so next node points back to current

head.next = null;

set current node's next to null to mark new tail

return newHead;

return new head of reversed list up the call stack

Output

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

Reversed list: 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 (head is null)

returns null immediately without error

DSA Java

if (head == null || head.next == null) {

single node list

returns the single node as is

DSA Java

if (head == null || head.next == null) {

When to Use This Pattern

When you see a problem asking to reverse a linked list and recursion is allowed, use the recursive reversal pattern by reversing the rest first and then flipping links on the way back.

Common Mistakes

Mistake: Not setting head.next to null after flipping the link, causing cycles
Fix: Always set head.next = null after reversing the link to mark the new tail

Mistake: Returning head instead of newHead, losing the new list head
Fix: Return the newHead obtained from recursive call, not the current head

Summary

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

Use when you want a clean, elegant recursive solution to reverse a linked list.

The key is to reverse the rest first, then flip the current node's link and set its next to null.

Practice

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

easy

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

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

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

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

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 after recursive call

   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 A

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
• Reversing pointers before recursive call
• 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 null.next;

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

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

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

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when list is empty or has one node, so head is null or head.next is null.

2. Step 2: Check each option

   if (head == null || head.next == null) return head; correctly returns head when list is empty or single node. Others cause errors or wrong returns.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Returning null when list has one node
• Accessing next of null causing errors
• Missing base case leading to infinite recursion

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. null

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

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

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

Solution

1. Step 1: Trace recursion on list 1->2->3

   Recursion goes to last node 3, then reverses links backward: 3 points to 2, 2 points to 1.

2. Step 2: Final reversed list

   After fixing pointers, the list becomes 3 -> 2 -> 1 -> null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option C

4. Quick Check:

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

Hint: Last node becomes new head after recursion [OK]

Common Mistakes:

• Not setting head.next to null causing cycle
• Returning old head instead of new head
• Confusing node values with pointers

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. head.next.next = head; should be head.next = head.next.next;

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

C. Return statement should be 'return head;' instead of newHead

D. No error; code is correct

Solution

1. Step 1: Check base case correctness

   Base case only checks head == null, missing single node case causes null pointer error at head.next.next.

2. Step 2: Fix base case

   Adding 'head.next == null' to base case prevents error and correctly stops recursion.

3. Final Answer:

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

4. Quick Check:

   Base case must handle single node [OK]

Hint: Base case must check single node to avoid null pointer [OK]

Common Mistakes:

• Ignoring single node base case causing runtime error
• Incorrect pointer assignment causing infinite loop
• Returning wrong node after recursion

5. Given a singly linked list with nodes 10 -> 20 -> 30 -> 40 -> null, you want to reverse it recursively but also count how many nodes were reversed. Which modification correctly adds counting nodes during recursion?

class Result {
  Node head;
  int count;
}

Result reverseCount(Node head) {
  if (head == null || head.next == null) {
    Result res = new Result();
    res.head = head;
    res.count = (head == null) ? 0 : 1;
    return res;
  }
  Result res = reverseCount(head.next);
  head.next.next = head;
  head.next = null;
  res.count += 1;
  return res;
}

hard

A. This code correctly reverses and counts nodes

B. Count should be incremented before recursive call

C. head.next = null; should be removed to avoid breaking list

D. Result class should store count as static variable

Solution

1. Step 1: Analyze recursive counting logic

   Base case sets count to 1 or 0. Each recursive return increments count by 1 after reversing pointer.

2. Step 2: Confirm correctness of pointer reversal and counting

   Pointer reversal is correct and count increments after recursion, so total nodes counted correctly.

3. Final Answer:

   This code correctly reverses and counts nodes -> Option A

4. Quick Check:

   Counting nodes during recursion works as coded [OK]

Hint: Increment count after recursion to count all nodes [OK]

Common Mistakes:

• Incrementing count before recursion causing wrong totals
• Removing head.next = null causing cycles
• Using static variable causing shared state bugs