1. What Is a Cycle in a Linked List?

A normal linked list ends when a node points to null. A cycle (also called a loop) exists when some node’s next pointer points back to an earlier node in the list — creating a loop that has no end.

Normal linked list (no cycle):
1 → 2 → 3 → 4 → 5 → null

Linked list with a cycle:
1 → 2 → 3 → 4 → 5
              ↑       |
              └───────┘
  (node 5's next points back to node 3)

In the cycled example, if you start at node 1 and keep following .next, you’ll visit: 1, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5 … forever. You’d never reach null.

2. Why Is a Cycle a Problem?

Cycles in linked lists are almost always bugs — usually caused by a coding mistake that accidentally connects a node back to a previous node. They cause:

• Infinite loops: Any traversal (printing, searching, length calculation) loops forever.
• Memory issues: Garbage collectors in some languages can’t reclaim cycled nodes because they always appear “reachable.”
• Wrong results: Algorithms like “find the last node” never terminate.

Detecting and removing cycles is therefore an important defensive programming skill and a favourite coding interview problem.

3. Three Ways to Detect a Cycle

Floyd’s algorithm is the gold standard. It’s what interviewers expect and what you should know cold.

4. Floyd’s Tortoise and Hare Algorithm

The intuition is beautifully simple: imagine two runners on a circular track. One runs slowly (1 lap/hour), the other runs fast (2 laps/hour). If the track is circular, the fast runner will eventually lap the slow runner and they’ll be at the same point again. If the track is straight (no loop), the fast runner just reaches the end first.

Applied to a linked list:

• Slow pointer (tortoise) — moves 1 node at a time.
• Fast pointer (hare) — moves 2 nodes at a time.

5. Visual Step-by-Step Trace

Let’s trace Floyd’s algorithm on this linked list:

Nodes:  1 → 2 → 3 → 4 → 5 → 6
                ↑               |
                └───────────────┘
(node 6's next points back to node 3)

Start: slow = 1, fast = 1

They meet at node 5. Cycle confirmed.

6. How to Find Where the Cycle Starts

Once we know a cycle exists (pointers met inside the cycle), we can find the exact node where the cycle begins. Here’s the trick:

1. Keep the fast pointer at the meeting point.
2. Reset the slow pointer back to the head of the list.
3. Move both pointers one step at a time.
4. Where they meet again = the start of the cycle.

Trace — Finding Cycle Start

After detection: slow = fast = node 5 (meeting point)
Reset slow to head (node 1). Fast stays at node 5.

Step 1: slow → 2,  fast → 6
Step 2: slow → 3,  fast → 3   ← Meet at node 3!

Cycle starts at node 3. ✓ (matches our diagram above)

7. Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def has_cycle(head):
    """Returns True if the linked list has a cycle."""
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

def find_cycle_start(head):
    """Returns the node where the cycle begins, or None."""
    slow = fast = head
    # Phase 1: detect
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle

    # Phase 2: find start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow  # cycle start node

# Build a test list: 1→2→3→4→5→6→(back to 3)
nodes = [Node(i) for i in range(1, 7)]
for i in range(5):
    nodes[i].next = nodes[i+1]
nodes[5].next = nodes[2]   # cycle: 6 → 3

print(has_cycle(nodes[0]))                    # True
print(find_cycle_start(nodes[0]).data)        # 3

8. Time and Space Complexity

Floyd’s algorithm is linear in time: in the worst case, the slow pointer travels n steps before meeting the fast pointer (which has done at most 2n steps). Only two pointer variables are used — no arrays, sets, or extra nodes — so space is O(1).

9. Worked Examples

Example 1 — No Cycle

List: 1 → 2 → 3 → null

slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=null → fast is null, STOP.
Result: No cycle. ✓

Example 2 — Entire List Is a Cycle

List: 1 → 2 → 3 → (back to 1)

slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=2
Step 3: slow=1, fast=1 → Meet! Cycle detected.
Cycle start: reset slow=head(1), fast stays at 1.
They already meet at node 1 → cycle starts at node 1. ✓

Example 3 — Single Node Pointing to Itself

List: 1 → (back to 1)

slow=1, fast=1
Step 1: slow=1 (1→1), fast=1 (1→1→1) → slow==fast.
Cycle detected immediately. Cycle start = node 1. ✓

10. Five Common Mistakes

Mistake 1 — Not checking fast.next before moving fast two steps

The fast pointer moves as fast.next.next. If fast.next is null, accessing fast.next.next throws a NullPointerException. Always check if fast and fast.next before each step.

Mistake 2 — Starting fast at head.next instead of head

Some implementations start slow at head and fast at head.next. This works but complicates the cycle-start-finding phase. Starting both at head is simpler and avoids off-by-one bugs.

Mistake 3 — Using a hash set and comparing node values, not node references

If your linked list contains duplicate values (e.g., 1 → 2 → 1), comparing values will give false positives. When using a hash set, store the node object reference (memory address), not the data value.

Mistake 4 — Forgetting the cycle-start-finding is a separate phase

Many beginners think the meeting point of slow and fast IS the cycle start. It’s not — it’s just somewhere inside the cycle. You need the second phase (reset slow to head, move both one step at a time) to find the actual cycle start.

Mistake 5 — Assuming the algorithm works for doubly linked lists without changes

Floyd’s algorithm assumes you only follow .next pointers. A doubly linked list with a cycle in its .prev pointers requires separate detection logic. For singly linked lists, the algorithm works as described.

11. Frequently Asked Questions

12. Next Steps