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?