Reverse a Singly Linked List Recursive in DSA Python

Mental Model

We flip the direction of each link by going to the end first, then reversing as we return back.

Analogy: Imagine unstacking a pile of plates one by one until the last plate, then stacking them back in reverse order.

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 goes deeper

Why: We go to the end before reversing links

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

head -> 1 -> 2 -> 3 -> null ↑ recursion goes deeper

Why: Keep going deeper to reach last node

Step 3: 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 4: reverse link: node 3 points back to node 2, node 2 next set to null

head -> 1 -> 2 ← 3 null ↑ reversing links

Why: Flip the link direction to reverse

Step 5: reverse link: node 2 points back to node 1, node 1 next set to null

head ← 1 ← 2 ← 3 null ↑ reversing links

Why: Continue flipping links as recursion unwinds

Step 6: return new head node 3 up to original call

3 -> 2 -> 1 -> null

Why: Final reversed list head returned

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA Python

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_recursive(head):
    if head is None or head.next is None:
        return head  # base case: empty or single node
    new_head = reverse_recursive(head.next)  # reverse rest
    head.next.next = head  # flip link of next node back to current
    head.next = None  # set current next to None to avoid cycle
    return new_head

def print_list(head):
    curr = head
    result = []
    while curr:
        result.append(str(curr.val))
        curr = curr.next
    print(" -> ".join(result) + " -> null")

# driver code
head = Node(1, Node(2, Node(3)))
print_list(head)
reversed_head = reverse_recursive(head)
print_list(reversed_head)

if head is None or head.next is None:

check base case: empty or single node list

new_head = reverse_recursive(head.next)

recursively reverse the rest of the list

head.next.next = head

flip the next node's next pointer back to current node

head.next = None

set current node's next to None to avoid cycle

return new_head

return new head of reversed list up the call stack

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 (head is None)

returns None immediately without error

DSA Python

if head is None or head.next is None:

single node list

returns the single node as is

DSA Python

if head is None or head.next is None:

When to Use This Pattern

When you see a problem asking to reverse a linked list recursively, think about reaching the end first then flipping links on the way back.

Common Mistakes

Mistake: Not setting head.next to None after flipping the link, causing cycles
Fix: Always set head.next = None after reversing the link to break old forward connection

Mistake: Returning head instead of new_head after recursion
Fix: Return new_head which is the new head of reversed list from recursive calls

Summary

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

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

The key insight is to reverse the rest first, then flip the current node's link.

Practice

1. What does the recursive function to reverse a singly linked list primarily do at each step?

easy

A. It iterates through the list using a loop to reverse pointers.

B. It swaps the values of the first and last nodes only.

C. It reverses the rest of the list and then adjusts the current node's next pointer.

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 end (base case).

2. Step 2: Reverse pointers on return

   After reaching the end, it reverses the next pointer of the current node to point backward.

3. Final Answer:

   It reverses the rest of the list and then adjusts the current node's next pointer. -> Option C

4. Quick Check:

   Recursive reversal = reverse rest + fix pointers [OK]

Hint: Think: reverse rest first, then fix current pointer [OK]

Common Mistakes:

• Trying to swap node values instead of pointers
• Using loops instead of recursion
• Not handling the base case properly

2. Which of the following is the correct base case for a recursive function reversing a singly linked list?

easy

A. if head.next is None: return None

B. if head.next is None: return head.next

C. if head is None: return head.next

D. if head is None or head.next is None: return head

Solution

1. Step 1: Identify base case meaning

   The base case stops recursion when the list is empty or has one node.

2. Step 2: Check correct condition

   When head is None (empty) or head.next is None (single node), return head as reversed list.

3. Final Answer:

   if head is None or head.next is None: return head -> Option D

4. Quick Check:

   Base case = empty or single node [OK]

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

Common Mistakes:

• Returning None incorrectly for single node
• Missing the empty list check
• Returning head.next instead of head

3. What will be the output linked list after reversing recursively the list: 1 -> 2 -> 3 -> None?

medium

A. 1 -> 2 -> 3 -> None

B. 3 -> 2 -> 1 -> None

C. 2 -> 3 -> 1 -> None

D. None -> 3 -> 2 -> 1

Solution

1. Step 1: Trace recursive calls

   Function calls itself on 2 -> 3 -> None, then on 3 -> None (base case).

2. Step 2: Reverse pointers on return

   On return, 3 points to 2, 2 points to 1, and 1 points to None.

3. Final Answer:

   3 -> 2 -> 1 -> None -> Option B

4. Quick Check:

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

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

Common Mistakes:

• Not updating the last node's next pointer
• Returning original head instead of new head
• Confusing node values with pointers

4. Given this recursive reverse function, what is the error?

def reverse(head):
    if head is None:
        return None
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

medium

A. Base case misses single node check causing AttributeError

B. head.next.next = head causes infinite loop

C. head.next = None should be before recursive call

D. Function returns None always

Solution

1. Step 1: Analyze base case

   Base case only checks if head is None, but not if head.next is None (single node).

2. Step 2: Identify error cause

   When head.next is None, head.next.next causes AttributeError because head.next is None.

3. Final Answer:

   Base case misses single node check causing AttributeError -> Option A

4. Quick Check:

   Missing single node base case = error [OK]

Hint: Always check head.next is None in base case [OK]

Common Mistakes:

• Ignoring single node base case
• Changing pointers before recursion
• Returning None instead of new head

5. How would you modify the recursive reverse function to also return the tail node of the reversed list efficiently?

hard

A. Return a tuple (new_head, tail) and update tail during recursion

B. Use a global variable to track tail node

C. Traverse the reversed list again to find tail after recursion

D. Return only new_head and ignore tail

Solution

1. Step 1: Understand tail tracking need

   To get tail efficiently, return it along with new head during recursion.

2. Step 2: Modify function to return tuple

   Return (new_head, tail) from recursive calls and update tail as current node.

3. Step 3: Avoid extra traversal

   This avoids traversing reversed list again, improving efficiency.

4. Final Answer:

   Return a tuple (new_head, tail) and update tail during recursion -> Option A

5. Quick Check:

   Return (head, tail) tuple for efficiency [OK]

Hint: Return both head and tail as tuple in recursion [OK]

Common Mistakes:

• Using global variables causing side effects
• Traversing list again after reversal
• Ignoring tail node requirement