Cycle detection is the problem of finding if a path in a graph or linked list leads back to a previously visited node. In a Linked List, a cycle means the next pointer of the last node points back to one of the previous nodes, creating an infinite loop.

Imagine you're in a hedge maze:

1. Approach 1 (Breadcrumbs): You drop a breadcrumb at every turn. If you ever see a breadcrumb again, you're in a loop.
2. Approach 2 (Runner): You and your friend start at the entrance. Your friend runs twice as fast. If the maze is a loop, your friend will eventually catch up and tap you on the shoulder.

---

1. Hashing Approach ($O(n)$ Space)

The most intuitive way is to store every node we visit in a Set. Before moving to the next node, we check if it already exists in the Set.

• Pro: Very easy to understand and find the starting node of the cycle.
• Con: Uses $O(n)$ extra memory.

2. Floyd’s Cycle-Finding Algorithm ($O(1)$ Space)

The "Fast and Slow" approach mentioned in the previous module.

• The Catch: If they meet, a cycle exists.
• Finding the Start: Once they meet, move slow back to the head. Keep fast at the meeting point. Move both at the same speed (1 step). The point where they meet again is the Start of the Cycle.

3. Brent’s Algorithm

An alternative to Floyd's that can be faster in certain cases by increasing the "teleportation" distance of the fast pointer.

---

javascript Standard
/**
 * Detects a cycle and returns the starting node.
 * Returns null if no cycle exists.
 */
function detectCycleStart(head) {
  if (!head || !head.next) return null;

  let slow = head;
  let fast = head;

  // 1. Check if cycle exists
  let hasCycle = false;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      hasCycle = true;
      break;
    }
  }

  if (!hasCycle) return null;

  // 2. Find the start of the cycle
  // Move slow to head, leave fast at meeting point
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next; // Both move 1 step now
  }

  return slow; // The starting node
}

---

Why do cycles happen?

In real systems, cycles can be caused by bugs in pointer logic, corrupted database records, or intentional circular structures (like a Round Robin scheduler).

Pro-Tip

If an interviewer asks you to "Break the Cycle", first find the start node using the logic above, then find the node before the start node in the loop and set its next to null.

Questions to Practice

• Is Palindrome Linked List: Can be solved by finding the middle and checking for symmetry.
• Intersection of Two Linked Lists: Can be viewed as a cycle detection problem if you temporarily link the tail of one list to its head.