Detect Cycle in a Linked List

Cycle Detection in Linked Lists

Detecting a cycle in a linked list is a classic problem in data structures and often appears in technical interviews. A cycle (or loop) occurs when a node’s next pointer links back to a previous node, forming an infinite loop. Understanding how to detect loop in linked list efficiently is critical for solving real-world problems and optimizing memory and pointer management.

This lesson explains all popular methods, especially Floyd’s cycle detection algorithm, complete with Python code, explanations, and edge cases—so you're not just solving the problem.

What Is a Cycle in a Linked List?

A cycle in a linked list occurs when a node’s next pointer references an earlier node in the same list instead of null. In simpler terms, as you follow the pointers from one node to the next, you’ll eventually revisit a node you’ve already seen.

Imagine a singly linked list:

• 1 → 2 → 3 → 4 → 5 → 2 (again)

Node 5 points back to Node 2, creating a circular reference. This results in an infinite loop, which can crash programs or lead to memory issues.

Understanding the concept of repeated nodes and how a pointer cycle forms is foundational before diving into detection techniques.

Why Cycle Detection Is Important in Coding Interviews

Detecting cycles is a must-know because:

• It's frequently asked in FAANG interviews.
• It evaluates your understanding of pointers, memory allocation, and algorithm design.
• It builds problem-solving habits essential for more advanced topics like graph theory and garbage collection in programming.

Interviewers use it to gauge how well you handle common interview problems and how efficiently you implement cycle detection with minimal space.

Floyd’s Cycle Detection Algorithm (Tortoise and Hare)

Floyd’s algorithm, also known as the Tortoise and Hare algorithm, is the most efficient way to detect a cycle in a linked list.

How it works:

1. Use two pointers:
   • slow (tortoise) moves one step at a time.
   • fast (hare) moves two steps at a time.
2. If the list contains a cycle, slow and fast will eventually meet.
3. If there's no cycle, fast will reach the end (null).

This method is powerful due to:

• O(n) time complexity
• O(1) space complexity
• No need to modify the list or use extra data structures

Python Code to Detect Cycle in a Linked List

Here’s a clean Python implementation using Floyd’s cycle detection algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True  # Cycle detected

    return False  # No cycle

This code uses the two-pointer technique and provides a fast, memory-efficient way to detect loop in linked list.

How to Return the Starting Node of the Cycle

Floyd’s algorithm can also identify where the cycle starts:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def detectCycleStart(head):
    slow = head
    fast = head

    # First, check if a cycle exists
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            break
    else:
        return None  # No cycle

    # Second, find the cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # Starting node of the cycle

This second phase helps you pinpoint the cycle entry point, which is useful when fixing or debugging cyclic references.

Time and Space Complexity

Floyd’s Algorithm:

• Time Complexity: O(n) — Every node is visited at most twice.
• Space Complexity: O(1) — No additional data structures are used.

These metrics make Floyd’s algorithm optimal for detecting cycles in terms of efficiency.

Alternate Approaches: Using Hashing

While Floyd’s algorithm is the gold standard, you can also use a hash set to track visited nodes:

1
2
3
4
5
6
7
8
9
10
11
def hasCycleWithHashing(head):
    visited = set()
    current = head

    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next

    return False

Trade-offs:

• Time Complexity: O(n)
• Space Complexity: O(n)
• Pros: Simpler logic for beginners
• Cons: Consumes extra memory

Edge Cases to Consider in Cycle Detection

When writing code to detect cycle in linked list, always handle the following edge cases:

• Empty list: head is None
• Single node: Can point to itself or be standalone
• Two nodes: One pointing to another or forming a self-loop
• No cycle: Fully linear list ending in None
• Cycle at the beginning: First node loops to itself or its neighbor

Handling these cases ensures your implementation is robust and bug-free.

Common Mistakes and How to Avoid Them

• Not checking if fast or fast.next is None → leads to runtime errors.
• Misplacing pointer movements in loops → can skip the meeting condition.
• Modifying the list structure during detection → unexpected side effects.
• Forgetting early exit cases → causes unnecessary iterations or infinite loops.

Carefully structuring conditions and testing all edge cases helps avoid these pitfalls.

Related Interview Questions and Practice Problems

• Linked List Cycle II – Detect cycle and return entry point.
• Remove Loop in Linked List – Fix the list structure once a cycle is found.
• Find Middle of Linked List – Also uses two-pointer technique.
• Reverse a Linked List – Useful for mastering pointer operations.

Practicing these problems will reinforce your linked list manipulation skills and boost your interview readiness.

Conclusion: Cycle Detection in Linked Lists

Detecting a cycle in a linked list is more than just a coding problem—it’s a real-world challenge that improves your grasp of data structures, memory management, and pointer logic. With Floyd’s algorithm, you get a clean and space-efficient solution. With hashing, you gain intuitive understanding.

Master both. Understand edge cases. Practice the variations.

This is how you build deep expertise in solving linked list problems and succeed in interviews that demand algorithmic clarity and precision.