Detect Cycle in Linked List Floyd's Algorithm in DSA C - 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 NULL?

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 C

Node* slow = head;
Node* fast = head;
while (fast && 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 Pointer	fast Pointer	Check Condition	Visual State
1	Initialize pointers	Node1	Node1	fast and fast->next not NULL	┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │──→ │ data:2 │──→ │ data:3 │ │ next:──┼ │ next:──┼ │ next:──┼ └────────┘ └────────┘ └────────┘ head
2	Move slow by 1	Node2	Node1	fast and fast->next not NULL	Step 2: slow moves to Node2 ┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │──→ │ data:3 │ │ next:──┼──→ │ next:──┼ │ next:──┼ └────────┘ └────────┘ └────────┘ head
3	Move fast by 2	Node2	Node3	fast and fast->next not NULL	Step 3: fast moves to Node3 ┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼ └────────┘ └────────┘ └────────┘ head
4	Check slow == fast	Node2	Node3	No (Node2 != Node3)	Pointers not equal, continue
5	Move slow by 1	Node3	Node3	fast and fast->next not NULL	Step 5: slow moves to Node3 ┌────────┐ ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ data:3 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼ └────────┘ └────────┘ └────────┘ head
6	Move fast by 2	Node3	Node2	fast and fast->next not NULL	Step 6: fast moves to Node2 (cycle) ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ next:──┼──→ │ next:──┼──→ (cycle back to Node2) └────────┘ └────────┘ head
7	Check slow == fast	Node3	Node2	No (Node3 != Node2)	Pointers not equal, continue
8	Move slow by 1	Node2	Node2	fast and fast->next not NULL	Step 8: slow moves to Node2 ┌────────┐ ┌────────┐ │ data:1 │ │ data:2 │ │ next:──┼──→ │ next:──┼──→ (cycle) └────────┘ └────────┘ head
9	Move fast by 2	Node2	Node2	fast and fast->next not NULL	Step 9: fast moves to Node2 Pointers meet, cycle detected
10	Check slow == fast	Node2	Node2	Yes (Node2 == Node2)	Cycle detected, return true

💡 Pointers slow and fast meet at Node2, confirming a cycle

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	After Step 8	After Step 9	Final
slow	Node1	Node2	Node2	Node3	Node3	Node2	Node2	Node2
fast	Node1	Node1	Node3	Node3	Node2	Node2	Node2	Node2

Key Moments - 3 Insights

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

Moving fast pointer twice as fast ensures that if a cycle exists, fast will eventually catch slow inside the loop, as shown in steps 3, 6, and 9 in the execution_table.

What happens if fast or fast->next becomes NULL?

If fast or fast->next is NULL, it means the list ends and no cycle exists. This is checked before each move in the loop (see step 1 and exit condition).

Why do we check slow == fast after moving pointers?

Checking slow == fast after moving pointers detects if both pointers meet inside a cycle, confirming its presence (see steps 4, 7, and 10).

Visual Quiz - 3 Questions

Look at the execution_table, at which step do slow and fast pointers first meet?

A Step 9

B Step 7

C Step 4

D Step 10

💡 Hint

Check the 'Check slow == fast' column and 'Visual State' at steps 4, 7, 9, and 10.

According to variable_tracker, what is the position of fast pointer after Step 6?

A Node3

B Node2

C Node1

D NULL

💡 Hint

Look at the 'fast' row under 'After Step 6' in variable_tracker.

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

A It would move only one step at a time

B It would meet slow pointer

C It would eventually become NULL or fast->next would be NULL

D It would loop infinitely

💡 Hint

Refer to the exit condition in concept_flow and execution_table where fast or fast->next is NULL.

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 NULL (no cycle)
- If slow == fast at any point, cycle exists
- Time: O(n), Space: O(1)
- Efficient and widely used cycle detection method

Full Transcript

This visualization shows Floyd's cycle detection algorithm in a linked list. Two pointers, slow and fast, start at the head. Slow moves one node at a time, fast moves two. If the list has no cycle, fast or fast->next becomes NULL, ending the loop. If there is a cycle, fast eventually catches slow inside the loop. The execution table traces each pointer move and checks if they meet. The variable tracker records pointer positions after each step. Key moments clarify why pointers move at different speeds and why meeting means a cycle. The quiz tests understanding of pointer positions and loop exit conditions.