Reverse a Singly Linked List Recursive in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Linked List Reversal

What is the printed state of the linked list after reversing it recursively?

DSA Python

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

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

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

# Create linked list 1 -> 2 -> 3 -> 4 -> null
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)

head = reverse_recursive(head)
print_list(head)

A null

B 1 -> 2 -> 3 -> 4 -> null

C 4 -> 3 -> 2 -> 1 -> null

D 1 -> null

💡 Hint

Think about how the recursion unwinds and reverses the links one by one.

The recursive function reverses the linked list by moving to the end and then changing the next pointers backward. The final printed list is reversed.

❓ Predict Output

intermediate

Output when reversing a single-node list recursively

What is the printed state of the linked list after reversing a single-node list recursively?

DSA Python

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

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

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

# Create linked list 5 -> null
head = Node(5)

head = reverse_recursive(head)
print_list(head)

A 5 -> null

B null

C 5 -> 5 -> null

D Error: NoneType has no attribute 'next'

💡 Hint

A single-node list reversed is the same list.

The base case returns the head itself when the list has one node, so the output remains the same.

❓ Predict Output

advanced

Output of recursive reversal on empty list

What is the printed output when reversing an empty linked list recursively?

DSA Python

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

def print_list(head):
    if head is None:
        print('null')
        return
    current = head
    result = []
    while current:
        result.append(str(current.val))
        current = current.next
    print(' -> '.join(result) + ' -> null')

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

head = None
head = reverse_recursive(head)
print_list(head)

A Error: 'NoneType' object has no attribute 'next'

B null

C Empty list

D None

💡 Hint

Check the base case for empty list in the recursive function.

The function returns None for empty list and print_list prints 'null' for None head.

🔧 Debug

advanced

Identify the error in this recursive reversal code

What error will this code produce when reversing a linked list recursively?

DSA Python

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

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

# Create linked list 1 -> 2 -> null
head = Node(1)
head.next = Node(2)

head = reverse_recursive(head)

A RecursionError: maximum recursion depth exceeded

B AttributeError: 'NoneType' object has no attribute 'next'

C No error, works correctly

D TypeError: unsupported operand type(s)

💡 Hint

Check the line where the next pointer is assigned to itself.

The line 'head.next = head' creates a cycle causing infinite recursion leading to RecursionError.

🧠 Conceptual

expert

Why does the recursive reversal function set head.next.next = head?

In the recursive reversal of a singly linked list, why do we set 'head.next.next = head' before setting 'head.next = None'?

A To delete the current node from the list

B To break the link between current node and next node to avoid cycles

C To move the head pointer forward in the list

D To reverse the link by making the next node point back to the current node

💡 Hint

Think about how links are reversed step by step in recursion.

Setting 'head.next.next = head' reverses the direction of the link between two nodes, making the next node point back to the current node.