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

Reverse a Singly Linked List Recursive

📖 Scenario: You are working on a simple contact list app. The contacts are stored in a singly linked list, where each contact points to the next one. You want to reverse the order of contacts using a recursive method, so the last contact becomes the first.

🎯 Goal: Build a singly linked list with 4 contacts, then write a recursive function to reverse the list, and finally print the reversed list.

📋 What You'll Learn

Create a singly linked list with nodes containing these exact names in order: 'Alice', 'Bob', 'Charlie', 'Diana'

Write a recursive function called reverse_recursive that takes the head node and returns the new head of the reversed list

Use the recursive function to reverse the linked list

Print the reversed linked list in the format: 'Diana -> Charlie -> Bob -> Alice -> null'

💡 Why This Matters

🌍 Real World

Linked lists are used in many apps to store ordered data like contacts, playlists, or tasks. Reversing a list can help show data in reverse order or undo operations.

💼 Career

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

1

Create the singly linked list

Create a class called Node with an __init__ method that takes name and sets self.name = name and self.next = None. Then create 4 nodes with names 'Alice', 'Bob', 'Charlie', and 'Diana'. Link them in order so that head points to the node with 'Alice'.

DSA Python

# Define Node class and create linked list nodes
# Your code here

Hint

Start by defining the Node class with name and next attributes. Then create each node and link them by setting the next attribute.

2

Add a helper variable for recursion

Create a variable called new_head and set it to None. This will hold the head of the reversed list after recursion.

DSA Python

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

head = Node('Alice')
head.next = Node('Bob')
head.next.next = Node('Charlie')
head.next.next.next = Node('Diana')

# Create new_head variable for reversed list
# Your code here

Hint

Initialize new_head to None before writing the recursive function.

3

Write the recursive reverse function

Write a recursive function called reverse_recursive that takes a parameter node. If node is None or node.next is None, return node. Otherwise, call reverse_recursive(node.next) and store the result in new_head. Then set node.next.next = node and node.next = None. Finally, return new_head. After the function, set new_head = reverse_recursive(head).

DSA Python

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

head = Node('Alice')
head.next = Node('Bob')
head.next.next = Node('Charlie')
head.next.next.next = Node('Diana')

new_head = None

# Write recursive reverse_recursive function and call it
# Your code here

Hint

Use the base case when node is None or last node. Then reverse the rest recursively and fix the pointers.

4

Print the reversed linked list

Use a current variable to traverse the reversed list starting from new_head. Use a while loop to print each node's name followed by ' -> '. After the loop, print 'null' to mark the end.

DSA Python

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

head = Node('Alice')
head.next = Node('Bob')
head.next.next = Node('Charlie')
head.next.next.next = Node('Diana')

new_head = None

def reverse_recursive(node):
    if node is None or node.next is None:
        return node
    new_head = reverse_recursive(node.next)
    node.next.next = node
    node.next = None
    return new_head

new_head = reverse_recursive(head)

# Print reversed linked list
# Your code here

Hint

Traverse from new_head and print each name followed by ' -> '. End with 'null'.

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