Detect Cycle in Linked List Floyd's Algorithm in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

Floyd's Algorithm uses two pointers moving at different speeds (slow and fast). If there is a cycle, the fast pointer will eventually meet the slow pointer inside the cycle.

beginner

In Floyd's Cycle Detection Algorithm, what are the speeds of the two pointers?

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

intermediate

Why does the fast pointer eventually meet the slow pointer if a cycle exists?

Because the fast pointer moves faster inside the cycle, it will lap the slow pointer and meet it at some node within the cycle.

beginner

What does it mean if the fast pointer reaches the end (null) in Floyd's Algorithm?

It means there is no cycle in the linked list because the fast pointer can move freely to the end without looping back.

intermediate

How can you find the starting node of the cycle after detecting a cycle using Floyd's Algorithm?

After detecting a cycle, reset one pointer to the head and move both pointers one step at a time. The node where they meet is the start of the cycle.

In Floyd's Cycle Detection Algorithm, what happens if the fast pointer reaches null?

A A cycle is detected

B The slow pointer moves faster

C There is no cycle in the linked list

D The algorithm restarts

If the fast pointer reaches null, it means the list ends and no cycle exists.

What is the speed difference between the two pointers in Floyd's Algorithm?

A Both move 2 steps

B Slow moves 1 step, fast moves 2 steps

C Slow moves 2 steps, fast moves 1 step

D Both move 1 step

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

What does it mean if the slow and fast pointers meet inside the linked list?

A A cycle exists

B No cycle exists

C The list is empty

D The pointers are at the head

Meeting of slow and fast pointers inside the list confirms a cycle.

How do you find the start of the cycle after detection?

A Restart the algorithm

B Move fast pointer two steps until it reaches null

C Move slow pointer two steps until it reaches null

D Reset one pointer to head, move both one step until they meet

Resetting one pointer to head and moving both one step at a time finds the cycle start.

Which data structure is Floyd's Cycle Detection Algorithm used on?

A Linked List

B Array

C Stack

D Queue

Floyd's Algorithm is specifically designed to detect cycles in linked lists.

Explain how Floyd's Cycle Detection Algorithm works step-by-step.

Think about how the pointers move and meet inside the list.

Describe how to find the starting node of a cycle after detecting it with Floyd's Algorithm.

Focus on pointer movement after cycle detection.

Practice

1. What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

easy

A. Use two pointers moving at different speeds to detect a cycle

B. Count the number of nodes and check if it exceeds a limit

C. Reverse the linked list and check if it matches the original

D. Use a hash set to store visited nodes and check for repeats

Solution

1. Step 1: Understand Floyd's algorithm concept

   It uses two pointers, one moving fast (two steps) and one slow (one step).

2. Step 2: Detect cycle by pointer meeting

   If the fast pointer meets the slow pointer, a cycle exists in the linked list.

3. Final Answer:

   Use two pointers moving at different speeds to detect a cycle -> Option A

4. Quick Check:

   Two pointers at different speeds = cycle detection [OK]

Hint: Two pointers, slow and fast, meet if cycle exists [OK]

Common Mistakes:

• Thinking counting nodes detects cycle
• Assuming reversing list helps detect cycle
• Confusing hash set method with Floyd's algorithm

2. Which of the following is the correct way to move the fast pointer in Floyd's cycle detection?

easy

A. fast = fast.next

B. fast = fast.next.next

C. fast = fast.next.next.next

D. fast = fast.next.prev

Solution

1. Step 1: Understand fast pointer movement

   The fast pointer moves two steps at a time to catch up with the slow pointer.

2. Step 2: Identify correct syntax

   Moving two nodes ahead is done by fast = fast.next.next.

3. Final Answer:

   fast = fast.next.next -> Option B

4. Quick Check:

   Fast pointer moves two steps = fast.next.next [OK]

Hint: Fast pointer moves two nodes ahead using next.next [OK]

Common Mistakes:

• Moving fast pointer only one step
• Trying to move fast pointer three steps
• Using invalid pointer like prev in singly linked list

3. What will be the output of the following code snippet?

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

head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head.next  # cycle here

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

print(has_cycle(head))

medium

A. True

B. None

C. False

D. Error

Solution

1. Step 1: Analyze linked list structure

   Nodes 1->2->3 and then 3 points back to 2, creating a cycle.

2. Step 2: Trace Floyd's algorithm

   Slow and fast pointers will meet inside the cycle, so function returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Cycle exists, so output = True [OK]

Hint: Cycle means slow and fast pointers meet, so return True [OK]

Common Mistakes:

• Ignoring cycle creation line
• Assuming no cycle returns True
• Confusing None return with False

4. Find the error in the following Floyd's cycle detection code:

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

medium

A. No return statement for cycle detection

B. slow pointer moves two steps instead of one

C. Missing initialization of slow pointer

D. fast pointer moves only one step instead of two

Solution

1. Step 1: Check pointer movements

   Fast pointer should move two steps (fast = fast.next.next), but here it moves one step.

2. Step 2: Understand impact on cycle detection

   Moving one step slows fast pointer, so it may never meet slow pointer correctly.

3. Final Answer:

   fast pointer moves only one step instead of two -> Option D

4. Quick Check:

   Fast pointer must move two steps [OK]

Hint: Fast pointer must jump two nodes, not one [OK]

Common Mistakes:

• Moving fast pointer one step
• Confusing slow pointer movement
• Forgetting to check fast and fast.next

5. Given a linked list where the last node points back to the head (forming a cycle), how can Floyd's algorithm be adapted to find the node where the cycle begins?

hard

A. Use a hash set to store nodes and return the first repeated node

B. Count nodes until slow and fast meet, then return count as cycle start

C. After detecting cycle, reset slow to head and move both pointers one step until they meet

D. Reverse the linked list and check where reversal breaks

Solution

1. Step 1: Detect cycle using Floyd's algorithm

   Use slow and fast pointers to find meeting point inside cycle.

2. Step 2: Find cycle start node

   Reset slow to head, then move slow and fast one step at a time until they meet; meeting point is cycle start.

3. Final Answer:

   After detecting cycle, reset slow to head and move both pointers one step until they meet -> Option C

4. Quick Check:

   Reset slow and move both pointers one step to find cycle start [OK]

Hint: Reset slow to head, move both one step to find cycle start [OK]

Common Mistakes:

• Trying to count nodes to find cycle start
• Using reversal which doesn't help here
• Confusing hash set method with Floyd's approach