Reverse a Singly Linked List Recursive in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a singly linked list?

A singly linked list is a chain of nodes where each node has a value and a link to the next node. The last node points to null, showing the end of the list.

intermediate

What does it mean to reverse a singly linked list recursively?

It means to change the direction of the links between nodes using a function that calls itself until it reaches the end, then flips the links back as it returns.

beginner

In recursive reversal, what is the base case?

The base case is when the current node is null or the next node is null, meaning we reached the end or the list is empty. This stops the recursion.

intermediate

How does the recursive function reverse the links after reaching the base case?

After reaching the base case, the function returns the last node as the new head. Then, each call flips the next node's link to point back to the current node, reversing the list step by step.

beginner

What is the time complexity of reversing a singly linked list recursively?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the recursion.

What is the base case in recursive reversal of a singly linked list?

A When the list has more than two nodes

B When the head node is reached

C When the current node is null or its next is null

D When the list is empty and has no nodes

The recursion stops when the current node is null or the next node is null, indicating the end of the list.

What does the recursive function return after reversing the list?

A The new head of the reversed list

B The original head of the list

C The last node before reversal

D Null

The function returns the new head node, which was the last node before reversal.

How many times does the recursive function visit each node in the list?

A Depends on the list size

B Twice

C Three times

D Once

Each node is visited once during the recursion, making the time complexity O(n).

Which pointer is changed to reverse the link between two nodes in recursion?

A The head pointer

B The next pointer of the next node to point back to the current node

C The previous pointer of the current node

D The tail pointer

The next pointer of the next node is changed to point back to the current node, reversing the link.

What happens to the original head node after the list is reversed recursively?

A It becomes the last node and points to null

B It remains the head

C It is removed from the list

D It points to itself

The original head becomes the last node and its next pointer is set to null.

Explain step-by-step how recursion reverses a singly linked list.

Think about what happens when the function reaches the end and how it flips links on the way back.

Describe the role of the base case in recursive reversal of a singly linked list.

Why do we need a condition to stop calling the function again?

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