Detect Cycle in Linked List Floyd's Algorithm in DSA Javascript - Execution Trace

Concept Flow - Detect Cycle in Linked List Floyd's Algorithm

Start: slow = head, fast = head

↓

Move slow by 1 step

↓

Move fast by 2 steps

↓

Check if slow == fast?

No→Check if fast or fast.next is null?

↓

Cycle detected, exit

The slow pointer moves one step, fast pointer moves two steps. If they meet, a cycle exists. If fast reaches null, no cycle.

Execution Sample

DSA Javascript

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

Checks if a linked list has a cycle using two pointers moving at different speeds.

Execution Table

Step	Operation	slow Pointer Node	fast Pointer Node	Visual State	Pointer Movement Explanation
1	Initialize pointers	Node 1	Node 1	head → Node1 → Node2 → Node3 → Node4 → Node2 (cycle)	slow and fast start at head (Node 1)
2	Move slow by 1, fast by 2	Node 2	Node 3	head → Node1 → Node2 → Node3 → Node4 → Node2 (cycle)	slow moves to Node 2, fast moves to Node 3
3	Move slow by 1, fast by 2	Node 3	Node 2	head → Node1 → Node2 → Node3 → Node4 → Node2 (cycle)	slow moves to Node 3, fast moves to Node 2 (cycle back)
4	Move slow by 1, fast by 2	Node 4	Node 4	head → Node1 → Node2 → Node3 → Node4 → Node2 (cycle)	slow moves to Node 4, fast moves to Node 4; pointers meet
5	Check if slow == fast	Node 4	Node 4	Cycle detected	Pointers meet, cycle found, exit

💡 Pointers slow and fast meet at Node 4, confirming a cycle in the list.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
slow	Node 1	Node 2	Node 3	Node 4	Node 4
fast	Node 1	Node 3	Node 2	Node 4	Node 4

Key Moments - 3 Insights

Why do we move fast pointer by two steps and slow pointer by one step?

Moving fast pointer twice as fast ensures that if a cycle exists, fast will eventually catch up to slow inside the cycle, as shown in steps 2-4 of the execution_table.

What happens if the list has no cycle?

If no cycle exists, fast or fast.next will become null, causing the loop to exit without slow and fast meeting. This is checked in the while condition before moving pointers.

Why do we check slow === fast after moving pointers?

We check after moving because initially slow and fast start at the same node. The meeting after moves confirms a cycle, as seen in step 5 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, at which step do slow and fast pointers first point to the same node?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Check the 'slow Pointer Node' and 'fast Pointer Node' columns for when they match.

According to variable_tracker, what node is the fast pointer at after Step 3?

A Node 3

B Node 4

C Node 2

D Node 1

💡 Hint

Look at the 'fast' row under 'After Step 3' in variable_tracker.

If the linked list had no cycle, what would happen to the fast pointer in the execution_table?

A It would eventually become null or fast.next would be null

B It would meet slow pointer at some node

C It would move only one step at a time

D It would loop infinitely without meeting slow

💡 Hint

Refer to the exit condition in the concept_flow and the explanation in key_moments about no cycle.

Concept Snapshot

Detect cycle in linked list using Floyd's algorithm:
- Use two pointers: slow (1 step), fast (2 steps)
- Move pointers until they meet or fast reaches null
- If pointers meet, cycle exists
- If fast or fast.next is null, no cycle
- Efficient O(n) time, O(1) space

Full Transcript

This visualization shows Floyd's cycle detection in a linked list. Two pointers start at the head. Slow moves one node at a time, fast moves two nodes. If the list has a cycle, fast will eventually catch slow inside the cycle. The execution table traces each step, showing pointer positions and the linked list's visual state with a cycle from Node 4 back to Node 2. Variable tracker logs pointer positions after each step. Key moments clarify why pointers move at different speeds and what happens if no cycle exists. The quiz tests understanding of pointer positions and cycle detection logic.

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