Code Templates

Use these adaptable code templates as starting points for solving cycle detection problems. Each template includes the core structure with comments explaining the logic and common variations across different data structures.

1. Floyd’s Cycle Detection (Linked List)

The Tortoise and Hare algorithm is the standard for detecting cycles in linked lists. It uses O(1) space.

Code Breakdown

We use two pointers, slow and fast.

slow moves 1 step at a time.
fast moves 2 steps at a time.
If fast reaches the end (null), there is no cycle.
If fast meets slow, there is a cycle.

  graph LR
    subgraph "Pointer Movement"
    Start[Head] --> Slow[Slow: 1 step]
    Start --> Fast[Fast: 2 steps]
    Slow --> Meet{Meet?}
    Fast --> Meet
    Meet -- Yes --> Cycle[Cycle Detected]
    Meet -- No --> End[Continue]
    end

/**
 * Floyd's Tortoise and Hare Algorithm
 * Time: O(n), Space: O(1)
 */
function hasCycle(head) {
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) return true;
    }

    return false;
}

/**
 * Find cycle start node
 */
function detectCycle(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Phase 1: Detect cycle
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) break;
    }

    if (!fast || !fast.next) return null;

    // Phase 2: Find cycle start
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }

    return slow;
}

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def has_cycle(head: ListNode) -> bool:
    if not head or not head.next:
        return False

    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

def detect_cycle(head: ListNode) -> ListNode:
    if not head or not head.next:
        return None

    slow = fast = head

    # Phase 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break

    if not fast or not fast.next:
        return None

    # Phase 2: Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow

public class Solution {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; next = null; }
    }

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) return true;
        }

        return false;
    }

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }

        if (fast == null || fast.next == null) return null;

        // Phase 2: Find cycle start
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;

        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) return true;
        }

        return false;
    }

    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;

        ListNode *slow = head;
        ListNode *fast = head;

        // Phase 1: Detect cycle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) break;
        }

        if (!fast || !fast->next) return nullptr;

        // Phase 2: Find cycle start
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

type ListNode struct {
    Val int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            return true
        }
    }

    return false
}

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    slow, fast := head, head

    // Phase 1: Detect cycle
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break
        }
    }

    if fast == nil || fast.Next == nil {
        return nil
    }

    // Phase 2: Find cycle start
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }

    return slow
}

class ListNode
  attr_accessor :val, :next
  def initialize(val)
    @val = val
    @next = nil
  end
end

def has_cycle(head)
  return false if head.nil? || head.next.nil?

  slow = head
  fast = head

  while fast && fast.next
    slow = slow.next
    fast = fast.next.next
    return true if slow == fast
  end

  false
end

def detect_cycle(head)
  return nil if head.nil? || head.next.nil?

  slow = head
  fast = head

  # Phase 1: Detect cycle
  while fast && fast.next
    slow = slow.next
    fast = fast.next.next
    break if slow == fast
  end

  return nil if fast.nil? || fast.next.nil?

  # Phase 2: Find cycle start
  slow = head
  while slow != fast
    slow = slow.next
    fast = fast.next
  end

  slow
end

2. DFS Cycle Detection (Directed & Undirected)

For graphs, DFS is robust.

Directed Graphs: We track recursion stack (visiting) vs fully visited. Back edge to “visiting” = cycle.
Undirected Graphs: We track parent. Edge to visited node that is NOT parent = cycle.

// Directed Graph
function hasCycleDirected(graph) {
    const visiting = new Set();
    const visited = new Set();

    function dfs(node) {
        if (visiting.has(node)) return true; // Cycle!
        if (visited.has(node)) return false;

        visiting.add(node);
        for (const neighbor of graph[node]) {
            if (dfs(neighbor)) return true;
        }
        visiting.delete(node);
        visited.add(node);
        return false;
    }

    for (let i = 0; i < graph.length; i++) {
        if (dfs(i)) return true;
    }
    return false;
}

// Undirected Graph
function hasCycleUndirected(graph) {
    const visited = new Set();

    function dfs(node, parent) {
        visited.add(node);
        for (const neighbor of graph[node]) {
            if (neighbor === parent) continue;
            if (visited.has(neighbor)) return true;
            if (dfs(neighbor, node)) return true;
        }
        return false;
    }

    for (let i = 0; i < graph.length; i++) {
        if (!visited.has(i) && dfs(i, -1)) return true;
    }
    return false;
}

# Directed Graph
def has_cycle_directed(graph):
    visiting = set()
    visited = set()

    def dfs(node):
        if node in visiting: return True
        if node in visited: return False

        visiting.add(node)
        for neighbor in graph[node]:
            if dfs(neighbor): return True

        visiting.remove(node)
        visited.add(node)
        return False

    for i in range(len(graph)):
        if dfs(i): return True
    return False

# Undirected Graph
def has_cycle_undirected(graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor == parent: continue
            if neighbor in visited: return True
            if dfs(neighbor, node): return True
        return False

    for i in range(len(graph)):
        if i not in visited and dfs(i, -1): return True
    return False

// Directed Graph
public boolean hasCycleDirected(List<List<Integer>> graph) {
    int[] state = new int[graph.size()]; // 0: unvisited, 1: visiting, 2: visited

    for (int i = 0; i < graph.size(); i++) {
        if (state[i] == 0 && dfsDirected(graph, state, i)) return true;
    }
    return false;
}

private boolean dfsDirected(List<List<Integer>> graph, int[] state, int node) {
    if (state[node] == 1) return true;
    if (state[node] == 2) return false;

    state[node] = 1;
    for (int neighbor : graph.get(node)) {
        if (dfsDirected(graph, state, neighbor)) return true;
    }
    state[node] = 2;
    return false;
}

// Undirected Graph
public boolean hasCycleUndirected(List<List<Integer>> graph) {
    boolean[] visited = new boolean[graph.size()];
    for (int i = 0; i < graph.size(); i++) {
        if (!visited[i] && dfsUndirected(graph, visited, i, -1)) return true;
    }
    return false;
}

private boolean dfsUndirected(List<List<Integer>> graph, boolean[] visited, int node, int parent) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (neighbor == parent) continue;
        if (visited[neighbor]) return true;
        if (dfsUndirected(graph, visited, neighbor, node)) return true;
    }
    return false;
}

// Directed Graph
bool hasCycleDirected(vector<vector<int>>& graph) {
    vector<int> state(graph.size(), 0); // 0: unvisited, 1: visiting, 2: visited

    function<bool(int)> dfs = [&](int node) {
        if (state[node] == 1) return true;
        if (state[node] == 2) return false;

        state[node] = 1;
        for (int neighbor : graph[node]) {
            if (dfs(neighbor)) return true;
        }
        state[node] = 2;
        return false;
    };

    for (int i = 0; i < graph.size(); i++) {
        if (state[i] == 0 && dfs(i)) return true;
    }
    return false;
}

// Undirected Graph
bool hasCycleUndirected(vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);

    function<bool(int, int)> dfs = [&](int node, int parent) {
        visited[node] = true;
        for (int neighbor : graph[node]) {
            if (neighbor == parent) continue;
            if (visited[neighbor]) return true;
            if (dfs(neighbor, node)) return true;
        }
        return false;
    };

    for (int i = 0; i < graph.size(); i++) {
        if (!visited[i] && dfs(i, -1)) return true;
    }
    return false;
}

// Directed Graph
func hasCycleDirected(graph [][]int) bool {
    state := make([]int, len(graph)) // 0: unvisited, 1: visiting, 2: visited

    var dfs func(int) bool
    dfs = func(node int) bool {
        if state[node] == 1 { return true }
        if state[node] == 2 { return false }

        state[node] = 1
        for _, neighbor := range graph[node] {
            if dfs(neighbor) { return true }
        }
        state[node] = 2
        return false
    }

    for i := range graph {
        if state[i] == 0 && dfs(i) { return true }
    }
    return false
}

// Undirected Graph
func hasCycleUndirected(graph [][]int) bool {
    visited := make([]bool, len(graph))

    var dfs func(int, int) bool
    dfs = func(node, parent int) bool {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if neighbor == parent { continue }
            if visited[neighbor] { return true }
            if dfs(neighbor, node) { return true }
        }
        return false
    }

    for i := range graph {
        if !visited[i] && dfs(i, -1) { return true }
    }
    return false
}

# Directed Graph
def has_cycle_directed(graph)
  visiting = Set.new
  visited = Set.new

  dfs = ->(node) {
    return true if visiting.include?(node)
    return false if visited.include?(node)

    visiting.add(node)
    graph[node].each do |neighbor|
      return true if dfs.call(neighbor)
    end
    visiting.delete(node)
    visited.add(node)
    return false
  }

  (0...graph.size).each do |i|
    return true if dfs.call(i)
  end
  false
end

# Undirected Graph
def has_cycle_undirected(graph)
  visited = Set.new

  dfs = ->(node, parent) {
    visited.add(node)
    graph[node].each do |neighbor|
      next if neighbor == parent
      return true if visited.include?(neighbor)
      return true if dfs.call(neighbor, node)
    end
    return false
  }

  (0...graph.size).each do |i|
    return true if !visited.include?(i) && dfs.call(i, -1)
  end
  false
end

3. Union-Find (Disjoint Set)

For undirected graphs, Union-Find is highly efficient. If the two nodes of an edge are already in the same set (same parent), adding the edge creates a cycle.

function hasCycleUnionFind(edges, n) {
    const parent = Array.from({length: n}, (_, i) => i);

    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]); // Path compression
        return parent[x];
    }

    for (const [u, v] of edges) {
        const rootU = find(u);
        const rootV = find(v);
        if (rootU === rootV) return true; // Cycle
        parent[rootU] = rootV;
    }
    return false;
}

def has_cycle_union_find(edges, n):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    for u, v in edges:
        root_u, root_v = find(u), find(v)
        if root_u == root_v:
            return True
        parent[root_u] = root_v
    return False

public boolean hasCycleUnionFind(int[][] edges, int n) {
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    for (int[] edge : edges) {
        int rootU = find(parent, edge[0]);
        int rootV = find(parent, edge[1]);
        if (rootU == rootV) return true;
        parent[rootU] = rootV;
    }
    return false;
}

private int find(int[] parent, int x) {
    if (parent[x] != x) parent[x] = find(parent, parent[x]);
    return parent[x];
}

bool hasCycleUnionFind(vector<vector<int>>& edges, int n) {
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);

    function<int(int)> find = [&](int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    };

    for (auto& edge : edges) {
        int rootU = find(edge[0]);
        int rootV = find(edge[1]);
        if (rootU == rootV) return true;
        parent[rootU] = rootV;
    }
    return false;
}

func hasCycleUnionFind(edges [][]int, n int) bool {
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    for _, edge := range edges {
        rootU := find(edge[0])
        rootV := find(edge[1])
        if rootU == rootV {
            return true
        }
        parent[rootU] = rootV
    }
    return false
}

def has_cycle_union_find(edges, n)
  parent = (0...n).to_a

  find = ->(x) {
    parent[x] = find.call(parent[x]) if parent[x] != x
    parent[x]
  }

  edges.each do |u, v|
    root_u = find.call(u)
    root_v = find.call(v)
    return true if root_u == root_v
    parent[root_u] = root_v
  end
  false
end

Common Variations

Collecting Cycle Nodes (JavaScript)

If you need to return all nodes involved in the cycle:

// Inside the detection loop when slow === fast
if (slow === fast) {
    const cycle = [];
    let temp = slow;
    do {
        cycle.push(temp.val);
        temp = temp.next;
    } while (temp !== slow);
    return cycle;
}

4. Edge Cases to Handle

Empty graphs: if (!graph || graph.length === 0)
Single nodes: if (n === 1)
No edges: Check for isolated nodes
Self-loops: if (u === v) return true;
Multiple components: Handle unvisited nodes

Interview Tips

Explain algorithm choice: Floyd’s for space constraints, DFS for general graphs
Understand graph representations: List vs matrix vs edge list
Handle variations: Cycle detection vs cycle start vs cycle length
Consider graph types: Directed vs undirected, weighted vs unweighted
Trade-offs: Time vs space, simplicity vs efficiency
Edge cases: Empty, single node, disconnected graphs

Remember: Always check for null/empty inputs and understand whether graphs are directed or undirected before choosing an algorithm.

Practice

Test your understanding by solving these problems: