Detect Cycle in Linked List Floyd's Algorithm in DSA C

Mental Model

Use two pointers moving at different speeds to find if a loop exists in a linked list.

Analogy: Imagine two runners on a circular track: one runs fast, the other slow. If the track loops, the fast runner will eventually catch the slow runner.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, with a cycle from node 5 back to node 3

Goal: Detect if the linked list contains a cycle using Floyd's algorithm

Step 1: Initialize slow and fast pointers at head (node 1)

1 -> 2 -> 3 -> 4 -> 5 ->
          ↑slow, ↑fast (both at node 1)

Why: Start both pointers at the beginning to begin traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast
          ↑slow

Why: Advance pointers at different speeds to detect cycle

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑fast
               ↑slow

Why: Continue advancing pointers; fast moves twice as fast

Step 4: Move slow by 1 step to node 4, fast by 2 steps from node 5 to node 4 (due to cycle)

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast, ↑slow

Why: Fast pointer loops back due to cycle; pointers meet

Step 5: Pointers slow and fast meet at node 4, cycle detected

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast, ↑slow (meeting point)

Why: Meeting point confirms presence of cycle

Result:

1 -> 2 -> 3 -> 4 -> 5 -> (cycle back to 3)
Cycle detected: true

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for singly linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect cycle using Floyd's algorithm
int detectCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // move slow by 1
        fast = fast->next->next; // move fast by 2

        if (slow == fast) {
            return 1; // cycle detected
        }
    }
    return 0; // no cycle
}

// Helper function to print list up to 10 nodes to avoid infinite loop
void printList(Node* head) {
    Node* temp = head;
    int count = 0;
    while (temp != NULL && count < 10) {
        printf("%d -> ", temp->data);
        temp = temp->next;
        count++;
    }
    if (temp != NULL) {
        printf("... (cycle detected)\n");
    } else {
        printf("null\n");
    }
}

int main() {
    // Create nodes
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // Create cycle: node 5 points back to node 3
    head->next->next->next->next->next = head->next->next;

    // Print list (limited)
    printList(head);

    // Detect cycle
    int hasCycle = detectCycle(head);
    if (hasCycle) {
        printf("Cycle detected: true\n");
    } else {
        printf("Cycle detected: false\n");
    }

    return 0;
}

while (fast != NULL && fast->next != NULL) {

continue loop while fast pointer and its next exist to avoid null dereference

slow = slow->next; // move slow by 1

advance slow pointer by one node

fast = fast->next->next; // move fast by 2

advance fast pointer by two nodes

if (slow == fast) { return 1; }

if pointers meet, cycle exists

Output

1 -> 2 -> 3 -> 4 -> 5 -> ... (cycle detected)

Cycle detected: true

Complexity Analysis

Time: O(n) because both pointers traverse the list at most once until they meet or reach the end

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to store visited nodes (O(n) space), Floyd's algorithm uses constant space making it more efficient

Edge Cases

Empty list (head is NULL)

Function returns no cycle immediately

DSA C

while (fast != NULL && fast->next != NULL) {

Single node with no cycle

Function returns no cycle as fast or fast->next is NULL

DSA C

while (fast != NULL && fast->next != NULL) {

Cycle at the beginning (node 1 points to itself)

Pointers meet quickly and cycle detected

DSA C

if (slow == fast) { return 1; }

When to Use This Pattern

When you need to check if a linked list loops back on itself, use Floyd's cycle detection because it finds cycles efficiently with two pointers moving at different speeds.

Common Mistakes

Mistake: Not checking if fast or fast->next is NULL before advancing fast pointer
Fix: Add condition 'while (fast != NULL && fast->next != NULL)' to avoid null pointer errors

Mistake: Moving slow and fast pointers by the same amount
Fix: Move slow by one step and fast by two steps to detect cycle properly

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you want to find if a linked list loops back on itself without extra memory.

The fast pointer will catch the slow pointer if a cycle exists, like runners on a circular track.

Practice

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

easy

A. To find the middle element of the linked list

B. To detect if there is a cycle (loop) in the linked list

C. To reverse the linked list

D. To sort the linked list in ascending order

Solution

1. Step 1: Understand Floyd's Algorithm goal

   Floyd's Cycle Detection Algorithm is designed to find if a linked list has a cycle or loop.

2. Step 2: Compare with other linked list operations

   Sorting, reversing, or finding the middle element are different operations and not related to cycle detection.

3. Final Answer:

   To detect if there is a cycle (loop) in the linked list -> Option B

4. Quick Check:

   Cycle detection = Detect cycle [OK]

Hint: Floyd's algorithm is famous for cycle detection [OK]

Common Mistakes:

• Confusing cycle detection with sorting
• Thinking it finds middle element
• Assuming it reverses the list

2. Which of the following is the correct way to initialize the two pointers used in Floyd's Cycle Detection Algorithm in C?

easy

A. Node *slow = head; Node *fast = head->next;

B. Node *slow = NULL; Node *fast = head;

C. Node *slow = head->next; Node *fast = head->next->next;

D. Node *slow = head; Node *fast = head;

Solution

1. Step 1: Understand pointer initialization in Floyd's algorithm

   Both slow and fast pointers start at the head node to begin traversal.

2. Step 2: Check options for correct initialization

   Node *slow = head; Node *fast = head; initializes both pointers at head, which is the standard approach.

3. Final Answer:

   Node *slow = head; Node *fast = head; -> Option D

4. Quick Check:

   Both pointers start at head [OK]

Hint: Both pointers start at head node in Floyd's algorithm [OK]

Common Mistakes:

• Starting fast pointer ahead of slow incorrectly
• Initializing slow as NULL
• Skipping initialization of one pointer

3. What will be the output of the following C code snippet using Floyd's algorithm on a linked list with a cycle?

typedef struct Node {
  int data;
  struct Node *next;
} Node;

int detectCycle(Node *head) {
  Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return 1;
  }
  return 0;
}

// Assume linked list has a cycle
printf("%d", detectCycle(head));

medium

A. 1

B. 0

C. Compilation error

D. Infinite loop

Solution

1. Step 1: Analyze the detectCycle function logic

   The function moves slow pointer by one and fast pointer by two nodes. If they meet, it returns 1 indicating a cycle.

2. Step 2: Given the list has a cycle, pointers will meet

   Since the list has a cycle, slow and fast pointers will eventually meet, so function returns 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Cycle present = return 1 [OK]

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

Common Mistakes:

• Assuming function returns 0 for cycle
• Thinking code causes infinite loop
• Confusing return values

4. Identify the bug in this Floyd's cycle detection code snippet:

int detectCycle(Node *head) {
  Node *slow = head, *fast = head;
  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next;
    if (slow == fast) return 1;
    fast = fast->next;
  }
  return 0;
}

medium

A. fast pointer moves two steps but not checked for NULL before second move

B. slow pointer moves two steps instead of one

C. fast pointer moves only one step instead of two

D. slow pointer is not initialized properly

Solution

1. Step 1: Analyze pointer movements in the loop

   Slow moves one step, fast moves one step, then checks if slow == fast, before the second fast move.

2. Step 2: Problem with check timing

   In Floyd's algorithm, fast should move two steps before the cycle check. Here, the check occurs after fast has moved only one step, and the second fast move is done without checking if fast->next is NULL, which can cause a NULL pointer dereference.

3. Final Answer:

   fast pointer moves two steps but not checked for NULL before second move -> Option A

4. Quick Check:

   Second fast move lacks NULL check [OK]

Hint: Fast pointer must complete two steps with NULL checks before cycle check [OK]

Common Mistakes:

• Checking cycle after fast's first step only
• Confusing slow and fast pointer steps
• Not initializing pointers correctly

5. You have a linked list where a cycle exists. After detecting the cycle using Floyd's algorithm, how can you find the starting node of the cycle?

hard

A. Move fast pointer two steps and slow pointer one step until they meet again

B. Count the number of nodes in the list and divide by two

C. Reset slow pointer to head, then move slow and fast one step at a time until they meet

D. Reverse the linked list and check for cycle again

Solution

1. Step 1: Detect cycle and pointers meet inside the loop

   Floyd's algorithm detects cycle when slow and fast pointers meet inside the loop.

2. Step 2: Reset slow to head and move both pointers one step at a time

   Reset slow to head, then move slow and fast one step each until they meet again; this meeting point is the cycle start.

3. Final Answer:

   Reset slow pointer to head, then move slow and fast one step at a time until they meet -> Option C

4. Quick Check:

   Reset slow + move both one step = cycle start [OK]

Hint: Reset slow to head, move both pointers stepwise to find cycle start [OK]

Common Mistakes:

• Moving fast pointer two steps again
• Trying to count nodes to find cycle start
• Reversing list to detect cycle start