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 Linked List with a Cycle

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

DSA C++

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = head->next; // cycle here
    bool result = hasCycle(head);
    if (result) std::cout << "Cycle detected" << std::endl;
    else std::cout << "No cycle" << std::endl;
    return 0;
}

A Compilation error

B No cycle

C Cycle detected

D Runtime error

💡 Hint

Remember that Floyd's algorithm uses two pointers moving at different speeds to detect cycles.

The linked list has a cycle because the last node points back to the second node. Floyd's algorithm detects this by the slow and fast pointers meeting inside the cycle, so the output is 'Cycle detected'.

❓ Predict Output

intermediate

Output of Floyd's Algorithm on a Linked List without a Cycle

What will the following C++ code print when Floyd's cycle detection algorithm is run on a linked list without any cycle?

DSA C++

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

int main() {
    Node* head = new Node(10);
    head->next = new Node(20);
    head->next->next = new Node(30);
    head->next->next->next = new Node(40);
    bool result = hasCycle(head);
    if (result) std::cout << "Cycle detected" << std::endl;
    else std::cout << "No cycle" << std::endl;
    return 0;
}

A Compilation error

B No cycle

C Segmentation fault

D Cycle detected

💡 Hint

Think about what happens when the fast pointer reaches the end of the list.

Since the linked list has no cycle, the fast pointer reaches the end (nullptr) and the function returns false, so the output is 'No cycle'.

🔧 Debug

advanced

Identify the Bug in Floyd's Cycle Detection Implementation

The following code is intended to detect a cycle in a linked list using Floyd's algorithm. What is the bug that causes it to fail or crash?

DSA C++

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

A The while loop condition should check if fast is not nullptr before accessing fast->next

B The function should return false inside the loop instead of after

C The slow pointer should move two steps instead of one

D The fast pointer should be initialized to head->next instead of head

💡 Hint

Check the order of pointer checks in the while loop condition to avoid null pointer dereference.

The condition fast->next assumes fast is not nullptr, but fast can be nullptr causing a crash. The correct condition is to check fast != nullptr before fast->next.

🧠 Conceptual

advanced

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

Why does Floyd's cycle detection algorithm use two pointers moving at different speeds (slow and fast) to detect a cycle in a linked list?

A Because if there is a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle

B Because the slow pointer alone can detect cycles by checking if it reaches the end

C Because the fast pointer moves slower to avoid skipping nodes

D Because two pointers moving at the same speed can detect cycles faster

💡 Hint

Think about how two runners on a circular track eventually meet if one runs faster.

The fast pointer moves twice as fast as the slow pointer. If a cycle exists, the fast pointer will lap the slow pointer inside the cycle, causing them to meet.

🚀 Application

expert

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

After detecting a cycle in a linked list using Floyd's algorithm, how can you find the node where the cycle begins?

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

B Reverse the linked list and check where the pointers meet

C Count the number of nodes in the list and divide by two to find the cycle start

D Reset one pointer to head and move both pointers one step at a time until they meet; the meeting point is the cycle start

💡 Hint

After detecting the cycle, resetting one pointer to head and moving both at the same speed helps locate the start.

Once slow and fast meet inside the cycle, resetting slow to head and moving both pointers one step at a time will cause them to meet at the cycle's starting node.

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 sort the linked list in ascending order

C. To reverse the linked list

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

Solution

1. Step 1: Understand Floyd's Algorithm goal

   Floyd's Cycle Detection Algorithm is designed to check if a linked list contains a cycle, meaning a node points back to a previous node.

2. Step 2: Compare with other linked list operations

   Sorting, reversing, or finding the middle element are different operations and not the purpose of this algorithm.

3. Final Answer:

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

4. Quick Check:

   Cycle detection = Detect cycle [OK]

Hint: Floyd's algorithm finds loops, not sorting or reversing [OK]

Common Mistakes:

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

2. Which of the following correctly initializes the two pointers used in Floyd's Cycle Detection Algorithm in C++?

easy

A. ListNode* slow = head; ListNode* fast = head;

B. ListNode* slow = head->next; ListNode* fast = head;

C. ListNode* slow = nullptr; ListNode* fast = head;

D. ListNode* slow = head; ListNode* fast = head->next;

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 each option

   ListNode* slow = head; ListNode* fast = head; initializes both pointers at head, which is the standard approach. Other options start pointers differently, which can cause errors or miss cycles.

3. Final Answer:

   ListNode* slow = head; ListNode* fast = head; -> Option A

4. Quick Check:

   Both pointers start at head [OK]

Hint: Start both pointers at head for Floyd's algorithm [OK]

Common Mistakes:

• Starting fast pointer at head->next causes skipping
• Initializing slow as nullptr causes null errors
• Swapping slow and fast initialization

3. What will be the output of the following code snippet detecting a cycle in a linked list?

#include <iostream>

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

bool hasCycle(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
  }
  return false;
}

int main() {
  Node a{1, nullptr};
  Node b{2, nullptr};
  Node c{3, nullptr};
  a.next = &b;
  b.next = &c;
  c.next = &b; // cycle here
  bool result = hasCycle(&a);
  std::cout << (result ? "Cycle detected" : "No cycle") << std::endl;
  return 0;
}

medium

A. No cycle

B. Cycle detected

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze linked list structure

   Nodes a, b, c are linked as a->b->c, and c points back to b, creating a cycle.

2. Step 2: Trace Floyd's algorithm behavior

   Slow and fast pointers will eventually meet inside the cycle, so hasCycle returns true.

3. Final Answer:

   Cycle detected -> Option B

4. Quick Check:

   Cycle exists, so output is "Cycle detected" [OK]

Hint: If a node points back, Floyd detects cycle [OK]

Common Mistakes:

• Ignoring the cycle created by c.next = &b
• Assuming no cycle because list looks linear
• Confusing output with compilation or runtime errors

4. Identify the bug in this Floyd's Cycle Detection code snippet:

bool detectCycle(Node* head) {
  Node* slow = head;
  Node* fast = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
  }
  return false;
}

medium

A. The return type should be void, not bool

B. Pointers slow and fast should start at different nodes

C. The while condition should check if fast is not nullptr before fast->next

D. The comparison if (slow == fast) should be outside the loop

Solution

1. Step 1: Check while loop condition safety

   The code checks fast->next and fast->next->next but does not check if fast itself is nullptr, risking null pointer access.

2. Step 2: Correct condition order

   Proper check is to ensure fast is not nullptr before accessing fast->next to avoid runtime errors.

3. Final Answer:

   The while condition should check if fast is not nullptr before fast->next -> Option C

4. Quick Check:

   Check fast != nullptr before fast->next [OK]

Hint: Always check pointer not null before accessing members [OK]

Common Mistakes:

• Skipping null check on fast pointer
• Starting pointers at different nodes unnecessarily
• Moving comparison outside loop causing infinite loop

5. Given a linked list where a cycle exists, how can Floyd's algorithm be extended to find the exact node where the cycle begins?

hard

A. After detecting the cycle, reset one pointer to head and move both pointers one step at a time until they meet at the cycle start.

B. Count the number of nodes in the list and divide by two to find the cycle start.

C. Use a hash set to store visited nodes and find the first repeated node.

D. Reverse the linked list and check where the reversal breaks to find the cycle start.

Solution

1. Step 1: Detect cycle using Floyd's algorithm

   First, detect the cycle by moving slow and fast pointers until they meet inside the cycle.

2. Step 2: Find cycle start node

   Reset one pointer to head, then move both pointers one step at a time; their meeting point is the cycle start node.

3. Final Answer:

   After detecting the cycle, reset one pointer to head and move both pointers one step at a time until they meet at the cycle start. -> Option A

4. Quick Check:

   Reset pointer + move stepwise = cycle start [OK]

Hint: Reset pointer to head after detection, move both stepwise [OK]

Common Mistakes:

• Trying to find cycle start by counting nodes
• Using extra memory like hash sets (not Floyd's method)
• Reversing list which breaks structure