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

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 and 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 5 back to 3

Goal: Detect if the linked list has 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 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 -> [slow->2] -> 3 -> [fast->3] -> 4 -> 5 ->
          ↑slow       ↑fast

Why: Slow moves one step, fast moves two steps to detect cycle faster

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

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

Why: Pointers advance to check if they meet inside the cycle

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

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

Why: Fast pointer loops back and meets slow pointer, confirming cycle

Result:

Cycle detected because slow and fast pointers meet at node 4

Annotated Code

DSA Javascript

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function detectCycle(head) {
  if (!head) return false;
  let slow = head;
  let 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 true; // cycle detected
    }
  }
  return false; // no cycle
}

// Create nodes
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
// Create cycle: 5 -> 3
head.next.next.next.next.next = head.next.next;

console.log(detectCycle(head));

while (fast !== null && fast.next !== null) {

continue loop while fast pointer and next node exist

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) {

check if slow and fast pointers meet indicating a cycle

return true; // cycle detected

return true immediately when cycle is found

Output

true

Complexity Analysis

Time: O(n) because each pointer traverses 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: Better than using a hash set which uses O(n) space; Floyd's algorithm uses constant space

Edge Cases

empty list

returns false immediately since no nodes exist

DSA Javascript

if (!head) return false;

single node without cycle

returns false because fast.next is null

DSA Javascript

while (fast !== null && fast.next !== null) {

single node with cycle (node points to itself)

detects cycle as slow and fast meet at the same node

DSA Javascript

if (slow === fast) {

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.

Common Mistakes

Mistake: Moving fast pointer by one step instead of two
Fix: Advance fast pointer by two steps to detect cycle faster

Mistake: Not checking if fast or fast.next is null before moving fast
Fix: Add condition to ensure fast and fast.next are not null before advancing

Mistake: Comparing slow and fast pointers incorrectly (e.g., comparing values instead of nodes)
Fix: Compare node references (slow === fast) to detect meeting point

Summary

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

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

The fast pointer will eventually catch the slow pointer if a cycle exists.

Practice

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

easy

A. To reverse the linked list

B. To sort the linked list in ascending order

C. To find the middle element of the linked list

D. To check if the linked list contains a cycle or loop

Solution

1. Step 1: Understand Floyd's Algorithm goal

   Floyd's Cycle Detection Algorithm is designed to detect if a linked list has 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 check if the linked list contains a cycle or loop -> Option D

4. Quick Check:

   Detect cycle = Check loop presence [OK]

Hint: Floyd's algorithm detects 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 is the correct way to initialize the two pointers in Floyd's Cycle Detection Algorithm in JavaScript?

easy

A. let slow = null; let fast = head;

B. let slow = head; let fast = head;

C. let slow = head; let fast = head.next;

D. let slow = head.next; let fast = head.next.next;

Solution

1. Step 1: Understand pointer initialization

   Slow pointer starts at head, fast pointer starts at head.next to allow fast to move two steps safely.

2. Step 2: Check pointer positions

   Starting fast at head.next prevents immediate equality and helps detect cycles correctly.

3. Final Answer:

   let slow = head; let fast = head.next; -> Option C

4. Quick Check:

   Slow at head, fast at head.next [OK]

Hint: Initialize slow at head and fast at head.next to detect cycles properly [OK]

Common Mistakes:

• Starting both pointers at head causing immediate equality
• Initializing slow pointer as null
• Starting pointers at incorrect nodes

3. Consider the following JavaScript code using Floyd's Algorithm to detect a cycle in a linked list:

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}

// Linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2)

What will be the output of hasCycle(head)?

medium

A. Runtime error

B. true

C. undefined

D. false

Solution

1. Step 1: Understand the linked list structure

   The list has a cycle because node with value 4 points back to node with value 2.

2. Step 2: Trace Floyd's Algorithm behavior

   Slow moves one step, fast moves two steps; they will meet inside the cycle, so function returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Cycle present = true [OK]

Hint: If pointers meet, cycle exists, so return true [OK]

Common Mistakes:

• Assuming no cycle returns true
• Confusing pointer equality with value equality
• Ignoring fast pointer null checks

4. The following code attempts to detect a cycle in a linked list using Floyd's Algorithm but has a bug:

function detectCycle(head) {
  let slow = head.next;
  let fast = head.next.next;
  while (fast && fast.next) {
    if (slow === fast) return true;
    slow = slow.next;
    fast = fast.next.next;
  }
  return false;
}

What is the main issue with this code?

medium

A. It does not check if head is null before accessing next

B. It starts slow and fast pointers ahead, missing cycles at head

C. It compares values instead of nodes for equality

D. It moves slow pointer two steps instead of one

Solution

1. Step 1: Analyze pointer initialization

   Code sets slow = head.next and fast = head.next.next without checking if head or head.next exist.

2. Step 2: Identify potential runtime error

   If head is null or head.next is null, accessing next properties causes runtime error.

3. Final Answer:

   It does not check if head is null before accessing next -> Option A

4. Quick Check:

   Missing null check causes runtime error [OK]

Hint: Always check head and next before pointer initialization [OK]

Common Mistakes:

• Ignoring null checks causing runtime errors
• Starting pointers incorrectly but missing null checks
• Confusing node equality with value equality

5. You have a linked list where a cycle exists, but you want to find the node where the cycle begins using Floyd's Algorithm. Which additional step should you perform after detecting the cycle?

hard

A. Reset one pointer to head, then move both pointers one step at a time until they meet

B. Continue moving fast pointer two steps and slow pointer one step until fast reaches null

C. Reverse the linked list and check for repeated nodes

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

Solution

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

   When slow and fast pointers meet, a cycle is confirmed.

2. Step 2: Find cycle start node

   Reset slow pointer to head, then move slow and fast one step at a time; their meeting point is the cycle start.

3. Final Answer:

   Reset one pointer to head, then move both pointers one step at a time until they meet -> Option A

4. Quick Check:

   Reset and move pointers to find cycle start [OK]

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

Common Mistakes:

• Continuing fast pointer movement after cycle detection
• Trying to reverse list to find cycle start
• Using node count to find cycle start incorrectly