Detect Cycle in Linked List Floyd's Algorithm in DSA Python - Execution Trace

Concept Flow - Detect Cycle in Linked List Floyd's Algorithm

Start: slow=head, fast=head

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if fast or fast.next is None?

Yes→No cycle, return False

No↓

Check if slow == fast?

Yes→Cycle detected, return True

↩Back to Move slow by 1 step

The algorithm uses two pointers moving at different speeds to detect if a cycle exists by checking if they meet.

Execution Sample

DSA Python

slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True
return False

This code moves two pointers through the list at different speeds to find if they meet, indicating a cycle.

Execution Table

Step	Operation	slow Node	fast Node	Pointer Changes	Visual State
1	Initialize slow and fast at head	Node 10	Node 10	slow=head, fast=head	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼─→ └────────┘ └────────┘ └────────┘ └────────┘ head
2	Move slow by 1 step	Node 20	Node 10	slow = slow.next	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼─→ └────────┘ └────────┘ └────────┘ └────────┘ head slow
3	Move fast by 2 steps	Node 20	Node 30	fast = fast.next.next	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│──→ │ data:30│──→ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼─→ └────────┘ └────────┘ └────────┘ └────────┘ head fast
4	Check slow == fast?	Node 20	Node 30	No match, continue loop	Pointers at different nodes, no cycle detected yet
5	Move slow by 1 step	Node 30	Node 30	slow = slow.next	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│──→ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼─→ └────────┘ └────────┘ └────────┘ └────────┘ head slow
6	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼─→ └────────┘ └────────┘ └────────┘ └────────┘ head fast
7	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, no cycle detected yet
8	Move slow by 1 step	Node 40	Node 40	slow = slow.next	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼─→ └────────┘ └────────┘ └────────┘ └────────┘ head slow
9	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next (cycle back to Node 30)	Cycle created: Node 40 points back to Node 30 Pointers: slow → Node 40 fast → Node 30
10	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
11	Move slow by 1 step	Node 30	Node 30	slow = slow.next (cycle back to Node 30)	Cycle continues: slow → Node 30 fast → Node 30
12	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next (cycle back to Node 40)	Cycle continues: slow → Node 30 fast → Node 40
13	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
14	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
15	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
16	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
17	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
18	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
19	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
20	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
21	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
22	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
23	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
24	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
25	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
26	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
27	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
28	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
29	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
30	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
31	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
32	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
33	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
34	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
35	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
36	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
37	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
38	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
39	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
40	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
41	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
42	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
43	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
44	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
45	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
46	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
47	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
48	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
49	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
50	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
51	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
52	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
53	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
54	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
55	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
56	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
57	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
58	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
59	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
60	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
61	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
62	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
63	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
64	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
65	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
66	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
67	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
68	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
69	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
70	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
71	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
72	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
73	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
74	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
75	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
76	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
77	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
78	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
79	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
80	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
81	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
82	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
83	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
84	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
85	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
86	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
87	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
88	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
89	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
90	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
91	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
92	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
93	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
94	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
95	Move slow by 1 step	Node 30	Node 30	slow = slow.next	Cycle continues: slow → Node 30 fast → Node 30
96	Move fast by 2 steps	Node 30	Node 40	fast = fast.next.next	Cycle continues: slow → Node 30 fast → Node 40
97	Check slow == fast?	Node 30	Node 40	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet
98	Move slow by 1 step	Node 40	Node 40	slow = slow.next	Cycle continues: slow → Node 40 fast → Node 40
99	Move fast by 2 steps	Node 40	Node 30	fast = fast.next.next	Cycle continues: slow → Node 40 fast → Node 30
100	Check slow == fast?	Node 40	Node 30	No match, continue loop	Pointers at different nodes, cycle detected but pointers not met yet

💡 The pointers slow and fast keep cycling through the loop nodes; when slow == fast, cycle is detected and function returns True.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
slow	Node 10	Node 20	Node 30	Node 40	Node 30	Node 40	Node 30	Cycle detected
fast	Node 10	Node 30	Node 40	Node 30	Node 40	Node 30	Node 40	Cycle detected

Key Moments - 3 Insights

Why do we move fast pointer by two steps and slow pointer by one step?

Moving fast pointer twice as fast ensures that if a cycle exists, fast will eventually catch up to slow inside the cycle, as shown in execution_table rows 2-7.

What happens if the list has no cycle?

If fast or fast.next becomes None, the loop ends and the function returns False, meaning no cycle. This is shown in the exit condition in concept_flow and execution_table.

Why do we check slow == fast inside the loop?

Because when slow and fast point to the same node, it means fast has caught slow inside the cycle, confirming a cycle exists. This is shown in execution_table steps where slow and fast meet.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which node is the fast pointer pointing to?

A Node 20

B Node 40

C Node 30

D Node 10

💡 Hint

Refer to execution_table row with Step 3 under 'fast Node' column.

At which step do slow and fast pointers first point to the same node?

A Step 11

B Step 5

C Step 1

D Step 2

💡 Hint

Check execution_table rows where 'slow Node' and 'fast Node' columns match.

If the list had no cycle, what would happen to the fast pointer?

A It would keep moving forever

B It would eventually become None or fast.next would be None

C It would move only one step at a time

D It would immediately equal slow pointer

💡 Hint

Refer to concept_flow where the check for fast or fast.next being None ends the loop.

Concept Snapshot

Detect Cycle in Linked List using Floyd's Algorithm:
- Use two pointers: slow (1 step), fast (2 steps)
- Move pointers until fast or fast.next is None (no cycle)
- If slow == fast at any point, cycle exists
- Return True if cycle found, else False
- Efficient O(n) time, O(1) space

Full Transcript

This concept shows how to detect a cycle in a linked list using Floyd's algorithm. Two pointers start at the head. Slow moves one step at a time, fast moves two steps. If the list has no cycle, fast or fast.next becomes None and the function returns False. If there is a cycle, fast will eventually catch slow inside the cycle, making slow equal fast, and the function returns True. The execution table traces each step, showing pointer positions and the linked list state. Key moments clarify why pointers move at different speeds and why the equality check is inside the loop.