Cycle Detection: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Cycle Detection: Complete Guide with Floyd's Algorithm

Welcome to the practice problems for cycle detection. If you need a refresher on the code, the code templates have Floyd’s algorithm, DFS state tracking, and Union-Find in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

Linked List Cycle teaches Floyd’s algorithm in its purest form. Master the two-pointer movement before adding the cycle-start math.
Find the Duplicate Number applies Floyd’s to an array, showing that the algorithm works on any sequence with a deterministic next-element function, not just linked-list nodes.
Linked List Cycle II extends Floyd’s with phase 2. Once you know a cycle exists, finding where it starts is the most common follow-up.
Course Schedule introduces graph cycle detection with DFS state tracking and Kahn’s algorithm. This is the most frequent interview variant.
Graph Valid Tree combines cycle detection with connectivity checking using Union-Find.
Longest Cycle in a Graph is the hardest problem in the set. It requires running DFS from every unvisited node and tracking discovery times, entry times, and cycle lengths.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Linked List Cycle

LeetCode 141 | Difficulty: Easy

Brief: Determine if a singly linked list has a cycle.

Why this pattern: This is Floyd’s tortoise and hare algorithm. Two pointers move at different speeds, and they meet if and only if a cycle exists.

Key Insight: The fast pointer gains one node on the slow pointer per iteration. If a cycle exists, the gap shrinks to zero and they meet. If the fast pointer reaches null, there is no cycle.

Visual:

    graph TD
    H["head"] --> N3["3"]
    N3 --> N2["2"]
    N2 --> N0["0"]
    N0 --> N_4["-4"]
    N_4 --> N2
    style N2 fill:#f9f,stroke:#333,stroke-width:2px

Code:

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

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

The null check on fast && fast.next at the top of the loop prevents a null reference error when fast reaches the end. The slow pointer catches up to fast when a cycle exists because fast moves two steps for every one step of slow, reducing the distance between them by one each iteration.

2. Find the Duplicate Number

LeetCode 287 | Difficulty: Easy (Medium on LeetCode, but conceptually straightforward with cycle detection)

Brief: Given an array of n+1 integers where each integer is between 1 and n, find the single duplicate number without modifying the array and using only

O(1)

extra space.

Why this pattern: The array values act as pointers to indices. This forms an implicit linked list where each value tells you the next index to visit. Floyd’s algorithm detects the cycle and finds its entry, which is the duplicate number.

Key Insight: Treat nums[i] as the next index to visit, like ListNode.next. The duplicate number is the entry point of the cycle, just like in Linked List Cycle II.

Visual:

    graph LR
    I0["Index 0: value 1"] --> I1["Index 1: value 3"]
    I1 --> I3["Index 3: value 2"]
    I3 --> I2["Index 2: value 4"]
    I2 --> I4["Index 4: value 2"]
    I4 --> I2
    style I2 fill:#f9f,stroke:#333,stroke-width:2px

Code:

var findDuplicate = function(nums) {
    let slow = nums[0];
    let fast = nums[0];

    // Phase 1: detect the cycle
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);

    // Phase 2: find the cycle entry (the duplicate)
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }

    return slow;
};

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = nums[0]

        # Phase 1: detect the cycle
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Phase 2: find the cycle entry
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: detect the cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: find the cycle entry
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        // Phase 1: detect the cycle
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // Phase 2: find the cycle entry
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

func findDuplicate(nums []int) int {
    slow := nums[0]
    fast := nums[0]

    // Phase 1: detect the cycle
    for {
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast {
            break
        }
    }

    // Phase 2: find the cycle entry
    slow = nums[0]
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

def find_duplicate(nums)
    slow = nums[0]
    fast = nums[0]

    # Phase 1: detect the cycle
    loop do
        slow = nums[slow]
        fast = nums[nums[fast]]
        break if slow == fast
    end

    # Phase 2: find the cycle entry
    slow = nums[0]
    while slow != fast
        slow = nums[slow]
        fast = nums[fast]
    end

    slow
end

The key insight is that nums[0] is always part of the cycle-initiating chain because 0 is outside the value range (1 to n), so no node points back to index 0. This guarantees that the entry point of the cycle is the duplicate value. The do-while loop runs phase 1 at least once, which avoids the initial slow === fast condition.

Medium Problems

3. Linked List Cycle II

LeetCode 142 | Difficulty: Medium

Brief: Return the node where the cycle begins in a linked list, or null if there is no cycle.

Why this pattern: Extends Floyd’s algorithm with a second phase. Once the fast and slow pointers meet, resetting one to head and moving both one step at a time locates the cycle entry.

Key Insight: The distance from head to the cycle start equals the distance from the meeting point to the cycle start. This is a provable property of the pointer movements.

Visual:

    graph LR
    S["Start (head)"] --> A["A"]
    A --> B["B"]
    B --> C["C"]
    C --> D["D"]
    D --> E["E"]
    E --> B
    style B fill:#f9f,stroke:#333,stroke-width:2px

Code:

var detectCycle = function(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;
        }
    }
    return null;
};

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and 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
        return None

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *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;
            }
        }
        return nullptr;
    }
};

def detectCycle(head)
    slow = 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
            end
            return slow
        end
    end
    nil
end

Phase 2 works because of a property of Floyd’s algorithm. If the distance from head to cycle start is D and the distance from the meeting point to cycle start (going forward) is M, then D = M. Resetting one pointer to head and moving both one step guarantees they converge on the cycle entry.

4. Course Schedule

LeetCode 207 | Difficulty: Medium

Brief: Determine if you can finish all courses given an array of prerequisite pairs, where [a, b] means you must take course b before course a.

Why this pattern: The prerequisites form a directed graph. A cycle in this graph means a circular dependency that makes the schedule impossible.

Key Insight: Kahn’s algorithm (topological sort using indegrees) processes courses with no remaining prerequisites. If some courses never reach zero indegree, a cycle blocks them.

Visual:

    graph TD
    A["Course 0"] --> B["Course 1"]
    B --> C["Course 2"]
    C --> A
    style A fill:#ff9999
    style B fill:#ff9999
    style C fill:#ff9999

Code:

var canFinish = function(numCourses, prerequisites) {
    const graph = Array.from({length: numCourses}, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, pre] of prerequisites) {
        graph[pre].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let visited = 0;
    while (queue.length) {
        const node = queue.shift();
        visited++;
        for (const neighbor of graph[node]) {
            indegree[neighbor]--;
            if (indegree[neighbor] === 0) queue.push(neighbor);
        }
    }

    return visited === numCourses;
};

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1

        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        visited = 0

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

        return visited == numCourses

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[numCourses];

        for (int[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        int visited = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            visited++;
            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) queue.offer(neighbor);
            }
        }

        return visited == numCourses;
    }
}

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);

        for (auto& edge : prerequisites) {
            graph[edge[1]].push_back(edge[0]);
            indegree[edge[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.push(i);
        }

        int visited = 0;
        while (!q.empty()) {
            int node = q.front(); q.pop();
            visited++;
            for (int neighbor : graph[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) q.push(neighbor);
            }
        }

        return visited == numCourses;
    }
};

func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    indegree := make([]int, numCourses)

    for _, edge := range prerequisites {
        graph[edge[1]] = append(graph[edge[1]], edge[0])
        indegree[edge[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    visited := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        visited++
        for _, neighbor := range graph[node] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    return visited == numCourses
}

def can_finish(num_courses, prerequisites)
    graph = Array.new(num_courses) { [] }
    indegree = Array.new(num_courses, 0)

    prerequisites.each do |course, pre|
        graph[pre] << course
        indegree[course] += 1
    end

    queue = (0...num_courses).select { |i| indegree[i] == 0 }
    visited = 0

    while !queue.empty?
        node = queue.shift
        visited += 1
        graph[node].each do |neighbor|
            indegree[neighbor] -= 1
            queue.push(neighbor) if indegree[neighbor] == 0
        end
    end

    visited == num_courses
end

Kahn’s algorithm trades the DFS state tracking for an indegree-based approach. The graph does not need to be traversed recursively. Instead, nodes enter the queue only when all their prerequisites are satisfied. If the count of processed nodes equals the total number of nodes, the graph is a DAG. A cycle would leave some nodes with non-zero indegree and they would never enter the queue.

5. Graph Valid Tree

LeetCode 261 | Difficulty: Medium

Brief: Given n nodes labeled from 0 to n-1 and a list of undirected edges, determine if the edges form a valid tree.

Why this pattern: A tree must be fully connected and contain no cycles. Union-Find detects cycles in undirected graphs efficiently, and a connectedness check confirms the single-component requirement.

Key Insight: A valid tree must have exactly n-1 edges. If it has more, a cycle exists. If it has fewer, the graph is disconnected. Union-Find detects the cycle by checking if two nodes of an edge already share a root.

Visual:

    graph TD
    A["0"] --- B["1"]
    A --- C["2"]
    B --- D["3"]
    D --- E["4"]
    style A fill:#bbf
    style E fill:#bbf

Code:

var validTree = function(n, edges) {
    if (edges.length !== n - 1) return false;
    const parent = Array.from({length: n}, (_, i) => i);

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

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

    return true;
};

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        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 False
            parent[root_u] = root_v

        return True

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] e : edges) {
            int rU = find(parent, e[0]), rV = find(parent, e[1]);
            if (rU == rV) return false;
            parent[rU] = rV;
        }
        return true;
    }

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

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);

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

        for (auto& e : edges) {
            int rU = find(e[0]), rV = find(e[1]);
            if (rU == rV) return false;
            parent[rU] = rV;
        }
        return true;
    }
};

func validTree(n int, edges [][]int) bool {
    if len(edges) != n-1 { return false }
    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 _, e := range edges {
        rU, rV := find(e[0]), find(e[1])
        if rU == rV { return false }
        parent[rU] = rV
    }
    return true
}

The edge count check edges.length !== n - 1 is a quick filter. A tree must have exactly n-1 edges. If it has more, a cycle is guaranteed. If it has fewer, the graph is disconnected. After that, Union-Find merges components as it processes edges. Finding two nodes that are already merged is the cycle signal.

Hard Problems

6. Longest Cycle in a Graph

LeetCode 2360 | Difficulty: Hard

Brief: You are given a directed graph of n nodes with each node having exactly one outgoing edge. Find the length of the longest cycle in the graph. If there is no cycle, return -1.

Why this pattern: Each node has exactly one outgoing edge, which means every node belongs to exactly one functional graph (a graph where each node has out-degree 1). This structure is composed of paths feeding into cycles. DFS with time tracking (entry times) finds cycle lengths.

Key Insight: When DFS encounters a node that has been visited in the current traversal, the difference between the current time and that node’s entry time is the cycle length.

Visual:

    graph TD
    N0["0"] --> N1["1"]
    N1 --> N2["2"]
    N2 --> N3["3"]
    N3 --> N1
    N4["4"] --> N5["5"]
    N5 --> N4
    style N1 fill:#f9f,stroke:#333,stroke-width:2px
    style N2 fill:#f9f,stroke:#333,stroke-width:2px
    style N3 fill:#f9f,stroke:#333,stroke-width:2px
    style N4 fill:#bbf,stroke:#333,stroke-width:2px
    style N5 fill:#bbf,stroke:#333,stroke-width:2px

Code:

var longestCycle = function(edges) {
    const n = edges.length;
    const visited = new Array(n).fill(false);
    const entryTime = new Array(n).fill(0);
    let maxLen = -1, time = 0;

    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;

        let node = i;
        const startTime = time;

        // Walk the path until we hit a visited node
        while (node !== -1 && !visited[node]) {
            visited[node] = true;
            entryTime[node] = time++;
            node = edges[node];
        }

        // If we hit a node we visited in THIS traversal, it is a cycle
        if (node !== -1 && entryTime[node] >= startTime) {
            maxLen = Math.max(maxLen, time - entryTime[node]);
        }
    }

    return maxLen;
};

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        visited = [False] * n
        entry_time = [0] * n
        max_len = -1
        time = 0

        for i in range(n):
            if visited[i]:
                continue

            node = i
            start_time = time

            # Walk the path until we hit a visited node
            while node != -1 and not visited[node]:
                visited[node] = True
                entry_time[node] = time
                time += 1
                node = edges[node]

            # If we hit a node from this traversal, it is a cycle
            if node != -1 and entry_time[node] >= start_time:
                max_len = max(max_len, time - entry_time[node])

        return max_len

class Solution {
    public int longestCycle(int[] edges) {
        int n = edges.length;
        boolean[] visited = new boolean[n];
        int[] entryTime = new int[n];
        int maxLen = -1;
        int time = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            int node = i;
            int startTime = time;

            while (node != -1 && !visited[node]) {
                visited[node] = true;
                entryTime[node] = time++;
                node = edges[node];
            }

            if (node != -1 && entryTime[node] >= startTime) {
                maxLen = Math.max(maxLen, time - entryTime[node]);
            }
        }

        return maxLen;
    }
}

class Solution {
public:
    int longestCycle(vector<int>& edges) {
        int n = edges.size();
        vector<bool> visited(n, false);
        vector<int> entryTime(n, 0);
        int maxLen = -1, time = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            int node = i;
            int startTime = time;

            while (node != -1 && !visited[node]) {
                visited[node] = true;
                entryTime[node] = time++;
                node = edges[node];
            }

            if (node != -1 && entryTime[node] >= startTime) {
                maxLen = max(maxLen, time - entryTime[node]);
            }
        }

        return maxLen;
    }
};

func longestCycle(edges []int) int {
    n := len(edges)
    visited := make([]bool, n)
    entryTime := make([]int, n)
    maxLen := -1
    time := 0

    for i := 0; i < n; i++ {
        if visited[i] { continue }

        node := i
        startTime := time

        for node != -1 && !visited[node] {
            visited[node] = true
            entryTime[node] = time
            time++
            node = edges[node]
        }

        if node != -1 && entryTime[node] >= startTime {
            cycleLen := time - entryTime[node]
            if cycleLen > maxLen {
                maxLen = cycleLen
            }
        }
    }

    return maxLen
}

def longest_cycle(edges)
    n = edges.length
    visited = Array.new(n, false)
    entry_time = Array.new(n, 0)
    max_len = -1
    time = 0

    (0...n).each do |i|
        next if visited[i]

        node = i
        start_time = time

        while node != -1 && !visited[node]
            visited[node] = true
            entry_time[node] = time
            time += 1
            node = edges[node]
        end

        if node != -1 && entry_time[node] >= start_time
            cycle_len = time - entry_time[node]
            max_len = cycle_len if cycle_len > max_len
        end
    end

    max_len
end

This problem combines DFS traversal with a timestamp technique. The entry_time array records when each node was first visited. The start_time variable resets for each new DFS component. When the traversal hits a node that has an entry_time at or after start_time, that node is part of the current traversal, meaning a cycle was found. The length of the cycle is current_time - entry_time[node]. The -1 edges represent nodes with no outgoing edge, which terminate the path.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These six problems cover the full range of cycle detection techniques. Start with the simple two-pointer application in Linked List Cycle and Find the Duplicate Number. Work through the graph variants in Course Schedule and Graph Valid Tree. Finish with the timestamp-based cycle length computation in Longest Cycle in a Graph. By the end, you should be able to recognize when a cycle detection approach applies and reach for the right algorithm.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .