Detect Cycle in Linked List Floyd's Algorithm in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind Floyd's Cycle Detection Algorithm in a linked list?

It uses two pointers moving at different speeds (slow and fast). If there is a cycle, the fast pointer will eventually meet the slow pointer inside the loop.

beginner

In Floyd's Algorithm, what speeds do the two pointers move at?

The slow pointer moves one step at a time, and the fast pointer moves two steps at a time.

intermediate

Why does the fast pointer eventually meet the slow pointer if a cycle exists?

Because the fast pointer moves faster, it will catch up to the slow pointer inside the cycle, like two runners on a circular track where the faster runner laps the slower one.

beginner

What is the time complexity of Floyd's Cycle Detection Algorithm?

The time complexity is O(n), where n is the number of nodes in the linked list.

beginner

What does it mean if the fast pointer reaches null in Floyd's Algorithm?

It means there is no cycle in the linked list because the fast pointer reached the end.

In Floyd's Cycle Detection Algorithm, what happens if the linked list has no cycle?

A The linked list becomes empty

B The slow pointer moves twice as fast

C The slow pointer meets the fast pointer

D The fast pointer reaches null

If there is no cycle, the fast pointer will reach the end (null) of the linked list.

What is the speed of the fast pointer in Floyd's Algorithm?

A Two steps at a time

B It does not move

C Three steps at a time

D One step at a time

The fast pointer moves two steps at a time to detect cycles efficiently.

Why do we use two pointers moving at different speeds in Floyd's Algorithm?

A To save memory

B To find the middle of the list

C To detect if a cycle exists by checking if they meet

D To reverse the linked list

Two pointers moving at different speeds help detect cycles by meeting inside the loop if a cycle exists.

What is the space complexity of Floyd's Cycle Detection Algorithm?

A O(n)

B O(1)

C O(log n)

D O(n^2)

Floyd's Algorithm uses constant extra space, O(1), because it only uses two pointers.

If the slow and fast pointers meet, what can we conclude?

A The linked list has a cycle

B The linked list has no cycle

C The linked list is empty

D The pointers are at the head

Meeting of slow and fast pointers means a cycle exists in the linked list.

Explain how Floyd's Cycle Detection Algorithm works to find a cycle in a linked list.

Think of two runners on a circular track.

Describe the time and space complexity of Floyd's Cycle Detection Algorithm and why it is efficient.

Focus on how many times pointers move and memory used.

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