Detect Cycle in Linked List Floyd's Algorithm in DSA Javascript - Build from Scratch

Detect Cycle in Linked List using Floyd's Algorithm

📖 Scenario: Imagine you are working on a system that manages a chain of tasks linked together. Sometimes, due to errors, a task might link back to an earlier task, creating a loop. This loop can cause the system to get stuck. Your job is to detect if such a loop exists in the chain.

🎯 Goal: You will build a linked list and use Floyd's Cycle Detection Algorithm to find out if there is a cycle (loop) in the linked list.

📋 What You'll Learn

Create a linked list with nodes having values 3, 2, 0, -4

Create a cycle by linking the last node back to the node with value 2

Implement Floyd's Cycle Detection Algorithm using two pointers named slow and fast

Print true if a cycle is detected, otherwise false

💡 Why This Matters

🌍 Real World

Detecting cycles in linked lists is important in systems like task schedulers, network routing, and memory management to avoid infinite loops and crashes.

💼 Career

Understanding cycle detection helps in debugging linked data structures and is a common interview question for software engineering roles.

1

Create the Linked List Nodes

Create a class called ListNode with a constructor that takes val and sets this.val and this.next to null. Then create four nodes named node1, node2, node3, and node4 with values 3, 2, 0, and -4 respectively. Link them in order: node1.next = node2, node2.next = node3, node3.next = node4.

DSA Javascript

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

// Create nodes and link them
// Your code here

Hint

Define the ListNode class first. Then create each node with the given values and link them by setting the next property.

2

Create the Cycle in the Linked List

Create a cycle by setting node4.next to node2 to link the last node back to the second node.

DSA Javascript

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

const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);

node1.next = node2;
node2.next = node3;
node3.next = node4;

// Create cycle by linking node4.next to node2
// Your code here

Hint

Set the next property of the last node to point back to the second node to form a loop.

3

Implement Floyd's Cycle Detection Algorithm

Create a function called hasCycle that takes head as input. Inside, create two pointers: slow and fast, both starting at head. Use a while loop that continues as long as fast and fast.next are not null. Inside the loop, move slow by one step (slow = slow.next) and fast by two steps (fast = fast.next.next). If at any point slow equals fast, return true. If the loop ends, return false.

DSA Javascript

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

const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);

node1.next = node2;
node2.next = node3;
node3.next = node4;

node4.next = node2;

// Implement hasCycle function using slow and fast pointers
// Your code here

Hint

Use two pointers moving at different speeds. If they meet, a cycle exists.

4

Print the Result of Cycle Detection

Call hasCycle with node1 as the argument and print the result using console.log.

DSA Javascript

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

const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);

node1.next = node2;
node2.next = node3;
node3.next = node4;

node4.next = node2;

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

// Print the result of hasCycle(node1)
// Your code here

Hint

Use console.log(hasCycle(node1)) to print the result.

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