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

Recall & Review

beginner

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

It 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 loop.

beginner

In Floyd's Algorithm, what speeds do the two pointers move at?

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, causing them to meet at some node within the loop.

beginner

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

It means the linked list has no cycle because the fast pointer reached the end of the list.

intermediate

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

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

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

A The linked list has no cycle

B The linked list has a cycle

C The slow pointer moves faster

D The algorithm fails

If the fast pointer reaches NULL, it means the list ends and there is no cycle.

What is the speed of the slow pointer in Floyd's Algorithm?

A Variable speed

B Two steps at a time

C One step at a time

D Three steps at a time

The slow pointer moves one node at a time.

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

A To reverse the linked list

B To detect if pointers meet inside a cycle

C To sort the linked list

D To find the length of the list

Different speeds help detect cycles by checking if pointers meet.

After detecting a cycle, how do you find the cycle's starting node?

A Count nodes until the end

B Move fast pointer two steps until it reaches NULL

C Reverse the linked list

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

Resetting one pointer to head and moving both pointers one step finds the cycle start.

What is the time complexity of Floyd's Cycle Detection Algorithm?

A O(n)

B O(n^2)

C O(log n)

D O(1)

The algorithm runs in linear time, O(n), where n is the number of nodes.

Explain step-by-step how Floyd's Cycle Detection Algorithm works to detect a cycle in a linked list.

Think about how the pointers move and what their meeting means.

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

Focus on pointer movement after detection.