Detect Cycle in Linked List Floyd's Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on a Linked List with a Cycle

What is the output of the following code that uses Floyd's algorithm to detect a cycle in a linked list?

DSA Python

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

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Create linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2)
head = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node2

print(has_cycle(head))

A RuntimeError

B True

C None

D False

💡 Hint

Remember that Floyd's algorithm returns True if slow and fast pointers meet inside the list.

The linked list has a cycle because node4 points back to node2. Floyd's algorithm detects this by slow and fast pointers meeting, so the output is True.

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on a Linked List without a Cycle

What is the output of the following code that uses Floyd's algorithm to detect a cycle in a linked list without a cycle?

DSA Python

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

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Create linked list: 1 -> 2 -> 3 -> 4 -> None
head = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = None

print(has_cycle(head))

A True

B IndexError

C None

D False

💡 Hint

If the fast pointer reaches the end, there is no cycle.

The linked list ends with None and has no cycle. Floyd's algorithm returns False because slow and fast pointers never meet.

🧠 Conceptual

advanced

Why does Floyd's Algorithm use two pointers moving at different speeds?

Why does Floyd's cycle detection algorithm use two pointers moving at different speeds (slow and fast) to detect a cycle in a linked list?

A Because both pointers move at the same speed to compare nodes

B Because the slow pointer moves faster to find the cycle quickly

C Because the fast pointer will eventually catch up to the slow pointer if there is a cycle

D Because the fast pointer skips nodes to reduce memory usage

💡 Hint

Think about what happens when two runners run around a circular track at different speeds.

The fast pointer moves two steps at a time and the slow pointer moves one step. If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle.

🔧 Debug

advanced

Identify the error in this Floyd's cycle detection implementation

What error will this code produce when trying to detect a cycle in a linked list?

DSA Python

def has_cycle(head):
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

A AttributeError

B TypeError

C No error, works correctly

D NameError

💡 Hint

Check what happens if head is None.

If head is None, fast is None, so fast.next causes AttributeError because None has no attribute 'next'.

🚀 Application

expert

Number of nodes in cycle after detection using Floyd's Algorithm

After detecting a cycle using Floyd's algorithm, how can you find the number of nodes in the cycle?

DSA Python

def count_cycle_nodes(meeting_point):
    count = 1
    current = meeting_point.next
    while current != meeting_point:
        current = current.next
        count += 1
    return count

# Assume meeting_point is the node where slow and fast pointers met inside the cycle

A Start from meeting_point and move until you return to it, counting nodes

B Count nodes from head until meeting_point

C Count nodes from head until None

D Count nodes from meeting_point to head

💡 Hint

The cycle length is the number of nodes in the loop starting and ending at the meeting point.

Starting at the meeting point, moving forward until you return to it counts all nodes in the cycle.