Detect Cycle in Linked List Floyd's Algorithm in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on a Cyclic List

What is the output of the following C code that uses Floyd's algorithm to detect a cycle in a linked list?

DSA C

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

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

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;
}

int main() {
    Node* head = malloc(sizeof(Node));
    Node* second = malloc(sizeof(Node));
    Node* third = malloc(sizeof(Node));
    head->data = 1; head->next = second;
    second->data = 2; second->next = third;
    third->data = 3; third->next = second; // cycle here

    printf("%d\n", detectCycle(head));
    return 0;
}

A 1

B 0

C Segmentation fault

D Compilation error

💡 Hint

Remember that Floyd's algorithm returns 1 if a cycle is detected.

The linked list has a cycle because third->next points back to second. Floyd's algorithm detects this and returns 1.

❓ Predict Output

intermediate

Output of Floyd's Cycle Detection on a Non-Cyclic List

What is the output of the following C code that uses Floyd's algorithm to detect a cycle in a linked list without a cycle?

DSA C

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

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

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;
}

int main() {
    Node* head = malloc(sizeof(Node));
    Node* second = malloc(sizeof(Node));
    Node* third = malloc(sizeof(Node));
    head->data = 1; head->next = second;
    second->data = 2; second->next = third;
    third->data = 3; third->next = NULL; // no cycle

    printf("%d\n", detectCycle(head));
    return 0;
}

A 1

B Compilation error

C Segmentation fault

D 0

💡 Hint

If there is no cycle, the function returns 0.

The linked list ends with NULL, so no cycle exists. The function returns 0.

🔧 Debug

advanced

Identify the Error in Cycle Detection Code

What error will this code produce when trying to detect a cycle in a linked list?

DSA C

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

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

A Compilation error due to pointer misuse

B Segmentation fault if head is NULL

C Infinite loop if list has no cycle

D No error, works correctly

💡 Hint

Check if the code handles empty list (head == NULL) safely.

If head is NULL, fast is NULL, so fast->next causes segmentation fault.

🧠 Conceptual

advanced

Why Floyd's Algorithm Uses Two Pointers Moving at Different Speeds?

Why does Floyd's cycle detection algorithm use two pointers moving at different speeds (slow and fast)?

A To guarantee that if a cycle exists, the fast pointer will eventually meet the slow pointer inside the cycle

B To ensure the fast pointer reaches the end faster for no cycle detection

C To reduce memory usage by avoiding extra data structures

D To sort the linked list while detecting cycles

💡 Hint

Think about how two pointers moving at different speeds behave in a cycle.

The fast pointer moves two steps while slow moves one step. If a cycle exists, they will meet inside the cycle.

🚀 Application

expert

Find the Starting Node of the Cycle Using Floyd's Algorithm

Given a linked list with a cycle, after detecting the cycle using Floyd's algorithm, how do you find the node where the cycle begins?

A Move fast pointer two steps and slow pointer one step until fast reaches NULL

B Reverse the linked list and check for repeated nodes

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

D Count the number of nodes in the list and divide by two

💡 Hint

After detecting the cycle, resetting slow to head helps locate the cycle start.

After detecting the cycle, resetting slow to head and moving both pointers one step at a time leads them to meet at the cycle start node.