Detect a linked-list cycle
Determine whether a singly linked list contains a cycle without storing every visited node.
Course progress
Problem 44 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
links = 1 -> 2 -> 3 -> 2
Expected output
True
What is happening?
A slow pointer advances one node while a fast pointer advances two. Because the list loops back to node 2, the pointers eventually meet.
Solution strategy
Build the right mental model
Move one pointer by one node and another by two. They must eventually meet inside a cycle; otherwise the faster pointer reaches the end.
Core concepts
linked list · fast and slow pointers
Complexity
Time O(n), space O(1).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for detect-linked-list-cycle
using System;
class Program
{
class Node
{
public int Value { get; private set; }
public Node Next { get; set; }
public Node(int value) { Value = value; }
}
static bool HasCycle(Node head)
{
Node slow = head;
Node 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 first = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
first.Next = second;
second.Next = third;
third.Next = second;
Console.WriteLine(HasCycle(first));
}
}Knowledge check
Questions students often ask
What is the main idea behind detect a linked-list cycle?
Move one pointer by one node and another by two. They must eventually meet inside a cycle; otherwise the faster pointer reaches the end.
What is the time and space complexity of this solution?
Time O(n), space O(1).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.