Detect if a Linked List is Circular in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a linked list to be circular?

A linked list is circular if the last node points back to any previous node in the list, creating a loop instead of ending with null.

intermediate

Which simple method can detect a circular linked list by using two pointers?

The Floyd’s Cycle-Finding Algorithm uses two pointers moving at different speeds (slow and fast). If they meet, the list is circular.

beginner

What is the role of the slow and fast pointers in detecting a circular linked list?

The slow pointer moves one step at a time, and the fast pointer moves two steps. If the list is circular, they will eventually meet inside the loop.

beginner

Why can't we just check if the next pointer is null to detect circular linked lists?

Because in a circular linked list, the next pointer never becomes null; it loops back to a previous node, so checking for null alone won't detect the loop.

intermediate

What is the time complexity of Floyd’s Cycle-Finding Algorithm for detecting a circular linked list?

The time complexity is O(n), where n is the number of nodes, because each pointer moves through the list at most a few times.

What happens if a linked list is not circular when using Floyd’s Cycle-Finding Algorithm?

A The algorithm runs forever

B The slow and fast pointers meet at some node

C The slow pointer reaches null first

D The fast pointer reaches null and the list is not circular

If the list is not circular, the fast pointer will reach the end (null), confirming no loop.

In Floyd’s Cycle-Finding Algorithm, how many steps does the fast pointer move compared to the slow pointer?

A Two steps

B One step

C Three steps

D Same number of steps

The fast pointer moves two steps at a time, while the slow pointer moves one step.

What is the main sign that a linked list is circular when using two pointers?

A The slow pointer reaches null

B The slow and fast pointers meet at the same node

C The fast pointer reaches null

D The list length is zero

If the slow and fast pointers meet, it means the list has a loop.

Which of these is NOT a characteristic of a circular linked list?

A No node has a null next pointer

B Contains a loop

C Last node points to null

D Traversal can continue indefinitely

In a circular linked list, the last node does NOT point to null; it points back to a previous node.

What is the space complexity of Floyd’s Cycle-Finding Algorithm?

A O(1)

B O(log n)

C O(n)

D O(n^2)

The algorithm uses only two pointers, so it requires constant extra space.

Explain how Floyd’s Cycle-Finding Algorithm detects a circular linked list step-by-step.

Think about how the pointers move and what it means when they meet.

Describe why a circular linked list can cause problems if not detected.

Imagine walking in a circle without stopping.