Going in Circles: Detecting Cycles in a Linked List for Coding Interviews

Introduction

A frequent problem posed in coding interviews involves identifying if a cycle exists within a linked list. Essentially, a cycle occurs if a node in a linked list points to a node that was traversed earlier in the list. This can create an infinite loop, potentially leading to issues in your code. In this blog post, we'll walk through the Floyd's Cycle Detection Algorithm (also known as the "tortoise and the hare" algorithm) to address this problem in Python.

Understanding Linked Lists

A linked list is a sequence of nodes where each node points to the next node in the sequence. It's a fundamental data structure that's widely used in computer science.

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

Floyd's Cycle Detection Algorithm

The most efficient way to detect a cycle in a linked list is by using Floyd's Cycle Detection Algorithm. This algorithm uses two pointers, one that moves two steps at a time (the "hare") and another that moves one step at a time (the "tortoise"). If a cycle exists, the fast pointer will eventually catch up to the slow pointer.

def has_cycle(head):
    if head is None:
        return False
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True  # A cycle was detected
    return False  # No cycle detected

This function will return True if a cycle is detected and False otherwise. The time complexity of this function is O(N), and the space complexity is O(1), where N is the number of nodes in the linked list.

Creating a Test Case

To test this function, you can create a linked list with a cycle:

# Creating a linked list with a cycle: 1->2->3->4->2...
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Creates the cycle
print(has_cycle(node1))  # Output: True

Conclusion

Detecting cycles in linked lists is a common task in coding interviews, and it's essential to understand how to do it efficiently. Floyd's Cycle Detection Algorithm provides an efficient solution with minimal space usage. This concept not only helps with linked list problems but also forms a basis for understanding other complex data structures and algorithms. As always, practice is the key to mastering these concepts. Happy coding!