Cycle detection

2 snippets in Interview Prep

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.

Detect Cycle in Graph

DSA · Graphs

syntax

Undirected: DFS — if we visit a node already visited (and it's not the parent), cycle exists.
Directed: Track 3 states — unvisited, in current path, completed.

example

// JavaScript — Directed graph cycle detection
function hasCycleDirected(graph, numNodes) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numNodes).fill(WHITE);
  function dfs(node) {
    color[node] = GRAY; // in current path
    for (const neighbor of (graph.get(node) || [])) {
      if (color[neighbor] === GRAY) return true; // back edge = cycle
      if (color[neighbor] === WHITE && dfs(neighbor)) return true;
    }
    color[node] = BLACK; // completed
    return false;
  }
  for (let i = 0; i < numNodes; i++) {
    if (color[i] === WHITE && dfs(i)) return true;
  }
  return false;
}

# Python — Directed graph
def has_cycle_directed(graph, num_nodes):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_nodes

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(num_nodes))

output

Cycle: 0→1→2→0 → True
No cycle: 0→1→2 → False

Note Time O(V + E), Space O(V). The three-color technique (white/gray/black) is standard for directed graphs. Gray = currently on the recursion stack. A back edge to a gray node proves a cycle. For undirected graphs, simply track parent to avoid false positives.