Cycle Detection: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Cycle Detection: Complete Guide with Floyd's Algorithm

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview.

Main Template: 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 by keeping only two pointers, regardless of the list length.

Use this for Linked List Cycle and Linked List Cycle II .

function hasCycle(head) {
    // Null or single-node lists cannot have a cycle
    if (!head || !head.next) return false;

    let slow = head;
    let fast = head;

    // The fast pointer moves twice as fast. If a cycle exists,
    // fast will lap slow before it ever reaches null.
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

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

    return false;
}

function detectCycle(head) {
    if (!head || !head.next) return null;

    let slow = head;
    let fast = head;

    // Phase 1: detect the 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 where the cycle begins.
    // The distance from head to cycle entry equals the distance
    // from the meeting point to cycle entry.
    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 the 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: reset one pointer to head and move both
    # one step at a time. They meet at the cycle entry.
    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 the 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: move both pointers one step at a time
        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 the 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 the cycle entry
        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 the 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 the cycle entry
    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 the 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 the cycle entry
  slow = head
  while slow != fast
    slow = slow.next
    fast = fast.next
  end

  slow
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

slow: moves one step per iteration. In the detection phase it probes each node in order. In the start-finding phase it resets to head.
fast: moves two steps per iteration. It is the probe that either reaches the end (no cycle) or laps the slow pointer (cycle found).
head: the starting reference. Resetting slow to head after detection is the key to finding the cycle entry.

Visual Mechanism

    stateDiagram-v2
    [*] --> Init: slow=head, fast=head
    Init --> Probe: fast != null && fast.next != null
    Probe --> Advance: slow=slow.next, fast=fast.next.next
    Advance --> Check: slow == fast?
    Check --> Found: Yes -> Cycle detected
    Check --> Probe: No -> Continue
    Probe --> NoCycle: fast or fast.next == null
    Found --> FindStart: slow=head
    FindStart --> Locate: slow != fast
    Locate --> AdvanceBoth: slow=slow.next, fast=fast.next
    AdvanceBoth --> Locate: Still not equal
    Locate --> Entry: slow == fast -> Cycle start
    NoCycle --> [*]
    Entry --> [*]

Critical Sections

The null check at the start handles empty and single-node lists. Without it, accessing head.next on a null reference throws an error.

The while loop condition fast && fast.next ensures the fast pointer never accesses null. If fast can make two moves, the list is long enough to check one more step.

Phase 2 relies on a mathematical property: the distance from the head to the cycle start equals the distance from the meeting point to the cycle start. Resetting one pointer to head and moving both one step at a time guarantees they converge at the entry node.

2. DFS Cycle Detection (Directed and Undirected)

For graph cycle detection, DFS with state tracking is the standard approach.

Directed graphs: track each node as unvisited, visiting (in the current recursion stack), or visited (fully processed). A back edge to a visiting node means a cycle.
Undirected graphs: track visited nodes and the parent of each node. A back edge to a visited node that is not the parent means a cycle.

Use this for Course Schedule and general graph cycle detection.

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

    function dfs(node) {
        if (visiting.has(node)) return true;  // back edge to active stack
        if (visited.has(node)) return false;  // already fully processed

        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;  // skip the edge we came from
            if (visited.has(neighbor)) return true;  // back edge = cycle
            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 Cycle Detection (Undirected Graphs)

For undirected graphs, Union-Find detects cycles without a DFS traversal. If two nodes of an edge already belong to the same set, adding that edge creates a cycle.

Use this for Graph Valid Tree .

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

    function find(x) {
        // Path compression flattens the tree so future
        // lookups are nearly constant time
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }

    for (const [u, v] of edges) {
        const rootU = find(u);
        const rootV = find(v);
        if (rootU === rootV) return true; // already connected = cycle
        parent[rootU] = rootV;
    }
    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
}

Variations

1. Topological Sort with Kahn’s Algorithm (Directed Graph)

Instead of DFS, Kahn’s algorithm uses indegrees to detect cycles. Nodes with indegree zero have no dependencies and can be processed first. If the graph has a cycle, some nodes will never reach indegree zero.

from collections import deque

def has_cycle_kahn(num_nodes, edges):
    graph = [[] for _ in range(num_nodes)]
    indegree = [0] * num_nodes

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = deque([i for i in range(num_nodes) if indegree[i] == 0])
    processed = 0

    while queue:
        node = queue.popleft()
        processed += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # If we could not process all nodes, a cycle exists
    return processed != num_nodes

2. Collecting Cycle Nodes

If you need the actual nodes in the cycle (not just a boolean), collect them after detection.

// After slow === fast in Floyd's algorithm
if (slow === fast) {
    const cycle = [];
    let temp = slow;
    do {
        cycle.push(temp.val);
        temp = temp.next;
    } while (temp !== slow);
    return cycle;
}

3. Happy Number (Floyd’s on Digits)

Floyd’s algorithm works on sequences where each element is derived from the previous one by a deterministic function, even without explicit linked-list nodes.

def is_happy(n: int) -> bool:
    def next_num(x):
        return sum(int(d) ** 2 for d in str(x))

    slow = n
    fast = next_num(n)

    while fast != 1 and slow != fast:
        slow = next_num(slow)
        fast = next_num(next_num(fast))

    return fast == 1

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .