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