Detecting Cycles in Linked Lists

The Problem: Cycle Detection

The formal problem statement is: "Given head, the head of a linked list, determine if the linked list has a cycle in it." You must return true if there is a cycle and false otherwise.

Before diving into the optimal solution, let's consider a more straightforward approach. How could we detect a node we've already seen? This thought process often leads to using a hash table (or a set in Python).

A Naive but Intuitive Solution: Using a Hash Set

The most direct way to check if you've visited a node before is to keep a record of every node you've seen. A hash set is perfect for this.

The algorithm would be:

1. Create an empty hash set, let's call it visited_nodes.
2. Start traversing the list from the head.
3. For each node you visit:
   • Check if the node is already in visited_nodes. If it is, you've found a cycle! Return true.
   • If it's not, add the node to visited_nodes and move to the next node.
4. If you reach the end of the list (None) without finding a duplicate, it means there is no cycle. Return false.

The following video explains this approach clearly.

As the video explains, this solution has:

• Time Complexity: $O(n)$, because we visit each node once.
• Space Complexity: $O(n)$, because in the worst case (a list with no cycle), we store every node in the hash set.

While this works, an interviewer will almost always follow up by asking: "Can you do it with $O(1)$ space?" This is where the Fast and Slow Pointer technique comes in.

The Optimal Solution: Floyd's Tortoise and Hare Algorithm

This elegant algorithm uses two pointers that move through the list at different speeds.

• A slow pointer (the "tortoise") moves one node at a time.
• A fast pointer (the "hare") moves two nodes at a time.

The logic is as follows:

1. Initialize both slow and fast pointers to the head of the list.
2. Move slow by one step and fast by two steps in each iteration.
3. If the list has no cycle, the fast pointer will reach the end (None) first. In this case, we can stop and return false.
4. If the list has a cycle, the fast pointer will enter the cycle and start lapping the slow pointer. Eventually, they are guaranteed to meet at the same node. When slow == fast, we've detected a cycle and can return true.

This article provides a great analogy to help you visualize this.

Why Are They Guaranteed to Meet?

This is the most important question to understand. It might seem possible for the fast pointer to "jump over" the slow pointer indefinitely. However, this is not the case.

Once both pointers are inside the cycle, the distance between them (in the direction of traversal) decreases by exactly one node with each step. Since the distance is a finite integer that decreases by one at a time, it is guaranteed to eventually become zero, meaning the pointers will meet.

Let's return to the video from 'take U forward', which provides an excellent mathematical intuition for this guarantee.

Python Implementation

Now, let's translate this logic into Python code. The implementation is surprisingly concise.

# Assume the ListNode class is defined as in the previous lesson
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def has_cycle(head: ListNode) -> bool:
    """
    Detects if a linked list has a cycle using Floyd's algorithm.
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return False
        
    slow = head
    fast = head
    



    # The loop condition is crucial: we must check `fast` and `fast.next`
    # to ensure we don't try to access `next` on a None object.
    while fast and fast.next:
        slow = slow.next          # Move 1 step
        fast = fast.next.next   # Move 2 steps
        



        # If they meet, a cycle exists
        if slow == fast:
            return True
            



    # If the loop finishes, fast reached the end, so no cycle
    return False




# --- Example Usage ---
# Create a list with a cycle: 1 -> 2 -> 3 -> 4 -> 2 (back to node 2)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Creates the cycle

print(f"Does the list have a cycle? {has_cycle(node1)}")  # Output: True




# Create a list without a cycle: 1 -> 2 -> 3 -> 4 -> None
nodeA = ListNode(1)
nodeB = ListNode(2)
nodeC = ListNode(3)
nodeD = ListNode(4)
nodeA.next = nodeB
nodeB.next = nodeC
nodeC.next = nodeD

print(f"Does the list have a cycle? {has_cycle(nodeA)}") # Output: False

Analysis and Interview Context

To be fully prepared for an interview, you need to understand the algorithm's performance and how to discuss it.

As the article confirms, the performance is:

• Time Complexity: $O(n)$. Although it might seem more complex, the slow pointer travels at most $n$ nodes before a collision or the end of the list is found.
• Space Complexity: $O(1)$. We only use two pointers, regardless of the list's size. This is the optimal space complexity and the main advantage of this algorithm.

Being able to explain these points and handle edge cases (like an empty list or a list with one node) will show your thorough understanding.

Conclusion

Excellent work today! You've added another essential algorithm to your interview preparation toolkit. You now know how to detect a cycle in a linked list using the highly efficient fast and slow pointer technique.

Key Takeaways:

• A cycle in a linked list is an infinite loop where a node points back to a previous node.
• A hash set provides an intuitive $O(n)$ space solution, but the optimal approach uses constant space.
• Floyd's Tortoise and Hare algorithm uses a slow pointer (1 step) and a fast pointer (2 steps). If there is a cycle, they are guaranteed to meet.
• The optimal solution has a time complexity of $O(n)$ and a space complexity of $O(1)$.

Preview of the Next Lesson:
In the next lesson, we will continue practicing for interviews by tackling a problem that requires you to solve a problem requiring a combination of data structures, such as a hash table and a list. This will test your ability to choose and integrate the right tools to solve a problem efficiently, a skill that is highly valued in technical interviews.