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

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 -> 3 (cycle)
fast ↑
slow ↑

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[slow, fast] -> 2 -> 3 -> 4 -> 5 -> back to 3

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 -> 2[slow] -> 3[fast] -> 4 -> 5 -> back to 3

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 -> 3[slow] -> 4 -> 5[fast] -> back to 3

Why: Fast pointer loops back due to cycle, slow pointer advances normally

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

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

Why: Fast pointer catches up to slow pointer inside the cycle

Step 5: Slow and fast pointers meet at node 4, cycle detected

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

Why: Pointers meeting means a cycle exists in the list

Result:

Cycle detected at node 4

Annotated Code

DSA Typescript

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
  }
}

function hasCycle(head: ListNode | null): boolean {
  if (!head) return false;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast && fast.next) {
    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
}

// Driver code to create list with cycle: 1->2->3->4->5->3
const node5 = new ListNode(5);
const node4 = new ListNode(4, node5);
const node3 = new ListNode(3, node4);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);
node5.next = node3; // create cycle

console.log(hasCycle(node1));

while (fast && fast.next) {

continue loop while fast pointer and its next exist to avoid null errors

slow = slow!.next; // move slow by 1

advance slow pointer by one node to traverse list slowly

fast = fast.next.next; // move fast by 2

advance fast pointer by two nodes to traverse list faster

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 both pointers traverse 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: Compared to using a hash set to store visited nodes (O(n) space), Floyd's algorithm uses constant space making it more efficient

Edge Cases

empty list (head is null)

function returns false immediately as there is no cycle

DSA Typescript

if (!head) return false;

list with one node and no cycle

function returns false as fast or fast.next becomes null quickly

DSA Typescript

while (fast && fast.next) {

list with two nodes and cycle (second node points back to first)

function detects cycle when slow and fast pointers meet

DSA Typescript

if (slow === fast) {

When to Use This Pattern

When you need to detect a cycle in a linked list efficiently without extra space, Floyd's cycle detection is the go-to pattern because it uses two pointers moving at different speeds to find loops.

Common Mistakes

Mistake: Advancing slow and fast pointers incorrectly, such as moving fast by only one step
Fix: Ensure fast pointer moves two steps each iteration to detect cycle properly

Mistake: Not checking if fast or fast.next is null before moving pointers
Fix: Add condition while (fast && fast.next) to avoid runtime errors

Summary

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

Use when you want to find cycles in linked lists efficiently without extra memory.

If a cycle exists, the fast pointer will eventually catch the slow pointer inside the loop.

Practice

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

easy

A. To find the middle element of the linked list

B. To sort the linked list in ascending order

C. To reverse the linked list

D. To detect if there is a cycle (loop) in the linked list

Solution

1. Step 1: Understand Floyd's Algorithm purpose

   Floyd's Cycle Detection Algorithm is designed to find if a linked list has a cycle by using two pointers moving at different speeds.

2. Step 2: Compare with other linked list operations

   Sorting, reversing, or finding the middle element are different operations and not the goal of Floyd's algorithm.

3. Final Answer:

   To detect if there is a cycle (loop) in the linked list -> Option D

4. Quick Check:

   Cycle detection = To detect if there is a cycle (loop) in the linked list [OK]

Hint: Floyd's algorithm uses two pointers to find loops fast [OK]

Common Mistakes:

• Confusing cycle detection with sorting or reversing
• Thinking it finds the middle element
• Assuming it modifies the list structure

2. Which of the following is the correct way to initialize the two pointers used in Floyd's Cycle Detection Algorithm in TypeScript?

easy

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

B. let slow = null; 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, and fast pointer starts at head.next to ensure fast moves ahead and cycle detection works correctly.

2. Step 2: Check other options

   Starting both at head may cause immediate equality if head is null or single node; starting slow at null or fast at head.next.next may cause errors.

3. Final Answer:

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

4. Quick Check:

   Fast pointer starts one step ahead [OK]

Hint: Fast pointer starts ahead to detect cycle properly [OK]

Common Mistakes:

• Starting both pointers at head causing false positives
• Initializing slow as null causing runtime errors
• Skipping nodes by wrong pointer start

3. Consider the following TypeScript code snippet using Floyd's algorithm to detect a cycle. What will be the output?

class Node {
  value: number;
  next: Node | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
head.next = node2;
node2.next = node3;
node3.next = node2; // cycle here

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

console.log(hasCycle(head));

medium

A. true

B. false

C. undefined

D. Runtime error

Solution

1. Step 1: Analyze the linked list structure

   The list has nodes 1 -> 2 -> 3, and node3 points back to node2, creating a cycle.

2. Step 2: Trace Floyd's algorithm execution

   Slow and fast pointers will eventually meet inside the cycle, causing the function to return true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle exists, so output is true [OK]

Hint: Cycle means slow and fast pointers meet [OK]

Common Mistakes:

• Ignoring the cycle and returning false
• Confusing pointer equality with value equality
• Missing the cycle created by node3.next = node2

4. The following TypeScript code attempts to detect a cycle in a linked list using Floyd's algorithm but does not work correctly. What is the error?

function detectCycle(head: Node | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next;
    if (slow === fast) return true;
  }
  return false;
}

medium

A. Missing null check for slow pointer

B. fast pointer moves only one step instead of two

C. slow pointer moves two steps instead of one

D. Incorrect comparison between slow and fast values

Solution

1. Step 1: Review pointer movements

   In Floyd's algorithm, fast pointer must move two steps each iteration, but here it moves only one step.

2. Step 2: Understand impact on cycle detection

   Moving fast only one step makes it move at the same speed as slow, so they may never meet, failing cycle detection.

3. Final Answer:

   fast pointer moves only one step instead of two -> Option B

4. Quick Check:

   Fast pointer must move two steps [OK]

Hint: Fast pointer must jump two nodes each loop [OK]

Common Mistakes:

• Moving fast pointer one step only
• Confusing slow and fast pointer speeds
• Not checking fast.next before moving fast

5. You have a singly linked list where the last node points back to the head, forming a cycle. Using Floyd's algorithm, how can you find the node where the cycle begins after detecting the cycle?

hard

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

B. Move both pointers two steps until they meet again

C. Count the number of nodes and divide by two to find the start

D. Reverse the linked list and check the first node

Solution

1. Step 1: Detect cycle with Floyd's algorithm

   First, detect the cycle by moving slow and fast pointers until they meet inside the loop.

2. Step 2: Find cycle start node

   Reset one pointer to head, then move both pointers one step at a time; the node where they meet is the cycle start.

3. Final Answer:

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

4. Quick Check:

   Reset and move one step to find cycle start [OK]

Hint: After detection, reset pointer and move both one step [OK]

Common Mistakes:

• Moving pointers two steps after detection
• Trying to count nodes to find cycle start
• Reversing list which breaks cycle detection