Tortoise hare

2 snippets in Interview Prep

Also written as tortoise and hare

DSAInterview Prep

Detect Cycle (Floyd's Tortoise & Hare)

syntax

Use slow (1 step) and fast (2 steps) pointers.
If they meet → cycle exists.
To find cycle start: reset one pointer to head, move both at 1 step.

example

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

function findCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow; // cycle start node
    }
  }
  return null;
}

# Python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

output

Has cycle: True/False
Cycle start: node where cycle begins

Note Time O(n), Space O(1). The math behind finding the cycle start: when they meet, the distance from head to cycle start equals the distance from meeting point to cycle start (going around). Always use 'is' (identity) not '==' (equality) for node comparison.

Pattern: Fast & Slow Pointer

DSA · Common Patterns Summary

syntax

When to use:
- Cycle detection (linked list, array)
- Finding middle of linked list
- Finding the start of a cycle
- Happy number problem

Slow moves 1 step, fast moves 2 steps.

example

// JavaScript — Happy number (sum of squared digits eventually reaches 1)
function isHappy(n) {
  function digitSquareSum(num) {
    let sum = 0;
    while (num > 0) {
      const digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }
  let slow = n, fast = n;
  do {
    slow = digitSquareSum(slow);
    fast = digitSquareSum(digitSquareSum(fast));
  } while (slow !== fast);
  return slow === 1;
}

# Python
def is_happy(n):
    def digit_square_sum(num):
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total
    slow = fast = n
    while True:
        slow = digit_square_sum(slow)
        fast = digit_square_sum(digit_square_sum(fast))
        if slow == fast:
            break
    return slow == 1

output

is_happy(19) → True (19→82→68→100→1)
is_happy(2) → False (enters cycle)

Note The fast/slow pointer pattern detects cycles in any sequence where each value maps to the next. It uses O(1) space compared to a hash set. For linked lists, this is Floyd's algorithm. For number sequences (like happy number), the function that generates the next value plays the role of 'next pointer'.