C# Program to Detect Cycle in Linked List

Use Floyd's Cycle Detection algorithm in C# by moving two pointers, slow and fast, through the linked list; if they meet, a cycle exists, e.g., bool HasCycle(Node head) { Node slow = head, fast = head; while (fast != null && fast.Next != null) { slow = slow.Next; fast = fast.Next.Next; if (slow == fast) return true; } return false; }.

Examples

InputLinked list: 1 -> 2 -> 3 -> 4 -> 5 (no cycle)

OutputNo cycle detected

InputLinked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2)

OutputCycle detected

InputEmpty linked list (null head)

OutputNo cycle detected

How to Think About It

To detect a cycle in a linked list, use two pointers moving at different speeds: one moves one step at a time (slow), the other moves two steps at a time (fast). If the list has a cycle, these pointers will eventually meet inside the cycle. If the fast pointer reaches the end (null), there is no cycle.

Algorithm

1

Start two pointers, slow and fast, at the head of the linked list.

2

Move slow pointer one step forward and fast pointer two steps forward in each iteration.

3

If at any point slow and fast pointers are equal, return true indicating a cycle.

4

If fast pointer reaches the end (null), return false indicating no cycle.

Code

csharp

using System;

class Node {
    public int Value;
    public Node Next;
    public Node(int value) { Value = value; Next = null; }
}

class Program {
    static bool HasCycle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.Next != null) {
            slow = slow.Next;
            fast = fast.Next.Next;
            if (slow == fast) return true;
        }
        return false;
    }

    static void Main() {
        Node head = new Node(1);
        head.Next = new Node(2);
        head.Next.Next = new Node(3);
        head.Next.Next.Next = new Node(4);
        head.Next.Next.Next.Next = new Node(5);
        // Create cycle for testing
        head.Next.Next.Next.Next.Next = head.Next; // cycle back to node with value 2

        Console.WriteLine(HasCycle(head) ? "Cycle detected" : "No cycle detected");
    }
}

Dry Run

Let's trace the linked list with nodes 1->2->3->4->5 and a cycle back to node 2 through the HasCycle method.

1

Initialize pointers

slow = node 1, fast = node 1

2

First iteration

slow moves to node 2, fast moves to node 3

3

Second iteration

slow moves to node 3, fast moves to node 5

4

Third iteration

slow moves to node 4, fast moves to node 3 (due to cycle)

5

Fourth iteration

slow moves to node 5, fast moves to node 5

6

Pointers meet

slow == fast at node 5, cycle detected

Iteration	Slow Pointer	Fast Pointer
Start	1	1
1	2	3
2	3	5
3	4	3
4	5	5

Why This Works

Step 1: Two pointers move at different speeds

The slow pointer moves one step, and the fast pointer moves two steps, so if a cycle exists, the fast pointer will eventually catch up to the slow pointer.

Step 2: Pointers meeting means cycle

When slow and fast pointers point to the same node, it means the list loops back, confirming a cycle.

Step 3: No cycle if fast pointer reaches end

If the fast pointer reaches null, it means the list ends normally without any cycle.

Alternative Approaches

Using a HashSet to track visited nodes

csharp

using System;
using System.Collections.Generic;

class Node {
    public int Value;
    public Node Next;
    public Node(int value) { Value = value; Next = null; }
}

class Program {
    static bool HasCycle(Node head) {
        var visited = new HashSet<Node>();
        Node current = head;
        while (current != null) {
            if (visited.Contains(current)) return true;
            visited.Add(current);
            current = current.Next;
        }
        return false;
    }

    static void Main() {
        Node head = new Node(1);
        head.Next = new Node(2);
        head.Next.Next = new Node(3);
        head.Next.Next.Next = new Node(4);
        head.Next.Next.Next.Next = new Node(5);
        head.Next.Next.Next.Next.Next = head.Next; // cycle

        Console.WriteLine(HasCycle(head) ? "Cycle detected" : "No cycle detected");
    }
}

This method uses extra memory to store visited nodes but is easier to understand.

Complexity: O(n) time, O(1) space

Time Complexity

The algorithm visits each node at most once with two pointers, so it runs in linear time O(n), where n is the number of nodes.

Space Complexity

It uses only two pointers and no extra data structures, so space complexity is constant O(1).

Which Approach is Fastest?

Floyd's algorithm is faster and uses less memory than the HashSet approach, which uses O(n) space.

Approach	Time	Space	Best For
Floyd's Cycle Detection	O(n)	O(1)	Memory efficient, fast detection
HashSet Tracking	O(n)	O(n)	Simple to implement, uses extra memory