Detect a Cycle in a Linked List

Table of Contents +

This one looks small. But the interviewer is watching for something specific. They want to see if you can spot a loop in a chain of nodes without running forever. So the real test is this. Can you find the trick that uses no extra memory? Let us talk it through the way you would in the room.

🔗 The Problem

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node. Normally the last node points to nothing, so the chain ends. But sometimes a node points back to an earlier node. Now the chain never ends. It just keeps going round and round. That is a cycle.

Your job is simple. Look at the head of the list and tell me this. Does the list have a cycle or not? Return true if it does. Return false if it does not.

List:  3 -> 2 -> 0 -> -4
            ^         |
            |_________|   (-4 points back to 2)


Input:  head = [3, 2, 0, -4], tail connects to node at index 1
Output: true


List:  1 -> 2 -> (null)
Input:  head = [1, 2]
Output: false

🐢 The Brute-Force Way

Here is the first idea most people get. As you walk the list, remember every node you have already seen. So you keep a set. A set is a box that stores things and never keeps copies. For each node you check one thing. Have I seen this node before?

If the node is already in the set, you came back to it. So there is a cycle. Return true. If you reach the end, meaning a node pointing to nothing, there was no loop. So return false.

This works fine. But see the problem. You are storing every node you visit. If the list has a million nodes, your set holds a million nodes. That is O(n) extra space. And the interviewer will ask you to do better.

🐇 The Optimal Way: Fast and Slow Pointers

This is the clever one. It is called Floyd’s cycle detection. But people love the nickname. The tortoise and the hare.

You use two pointers that walk the same list at different speeds. The slow pointer moves one node at a time. The fast pointer moves two nodes at a time. Now think about it like a running track. If the track is a straight line, the fast runner reaches the end and the race is over. No loop. But if the track is a circle, the fast runner keeps lapping the track. Sooner or later the fast runner catches the slow runner from behind. They meet.

So the rule is this. If fast and slow ever land on the same node, there is a cycle. If fast reaches the end of the list, there is no cycle.

Note

Why must they meet inside a loop? Once both pointers are inside the cycle, the fast pointer gains one step on the slow pointer every move. So the gap between them shrinks by one each time. A gap that keeps shrinking by one will hit zero. That is the moment they are on the same node.

📝 Steps to Solve It

  1. Start both slow and fast at the head of the list.
  2. Loop while fast is not null and fast.next is not null.
  3. Move slow forward by one node. Move fast forward by two nodes.
  4. After moving, check if slow and fast point to the same node. If yes, return true.
  5. If the loop ends (fast fell off the end), there is no cycle, so return false.
detect_cycle.py
# A node in the linked list
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


# Floyd's cycle detection: fast and slow pointers
def has_cycle(head):
    slow = head
    fast = head


    while fast is not None and fast.next is not None:
        slow = slow.next        # move one step
        fast = fast.next.next   # move two steps
        if slow is fast:        # they met, so there is a cycle
            return True
    return False  # fast reached the end, no cycle


# Build 3 -> 2 -> 0 -> -4, and link -4 back to node 2 (a cycle)
a = Node(3)
b = Node(2)
c = Node(0)
d = Node(-4)
a.next = b
b.next = c
c.next = d
d.next = b  # cycle here


print(has_cycle(a))


# Build 1 -> 2 with no cycle
x = Node(1)
y = Node(2)
x.next = y


print(has_cycle(x))

The output of the above code will be:

True
False

⏱️ Time and Space Complexity

Here is how the two approaches compare. The brute-force set is just as fast. But it pays a heavy price in memory.

Approach Time Space
Hash set of visited nodes O(n) O(n)
Fast and slow pointers (Floyd) O(n) O(1)

Tip

In the interview, mention the hash set idea first to show you understand the problem. Then say you can do it with O(1) space using two pointers. That jump from O(n) space to O(1) space is exactly what they want to hear.

🧩 Key Takeaways

  • ✅ A cycle means some node points back to an earlier node, so the chain never ends.
  • ✅ The simple fix is a hash set of visited nodes, but it costs O(n) extra space.
  • ✅ Floyd’s trick uses a slow pointer (one step) and a fast pointer (two steps).
  • ✅ If the two pointers ever meet, there is a cycle. If fast reaches the end, there is none.
  • ✅ Inside a loop the gap between fast and slow shrinks by one each move, so they must meet.
  • ✅ This gives you O(n) time and O(1) space, the answer the interviewer is looking for.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In Floyd's algorithm, how many nodes does the fast pointer move on each step?

    Why: The fast pointer moves two nodes per step while the slow pointer moves one, so the fast one can catch up inside a loop.

  2. 2

    What tells you the list has a cycle?

    Why: If the two pointers ever point to the same node, the fast pointer has lapped the loop and caught the slow pointer.

  3. 3

    Why is the fast and slow pointer method better than using a hash set?

    Why: Both are O(n) time, but the two-pointer method uses only constant extra space instead of storing every visited node.

  4. 4

    Inside a cycle, why must the two pointers eventually meet?

    Why: Once both are inside the loop, fast gains one step on slow every move, so the shrinking gap must reach zero.

Score: 0 / 4

🚀 What’s Next?

Previous Reverse a Linked List Next Find the Middle of a Linked List

Share & Connect

Share on LinkedIn