Write code to detect a cycle in a linked list.

Detecting Cycles in Linked Lists

Linked lists are fundamental data structures used in computer science. They're like chains of nodes, each pointing to the next. They're great for dynamic data where you need to add or remove items easily. But sometimes, things go wrong: a cycle can appear!

What's a Cycle?

A cycle in a linked list means the list loops back on itself. A node points back to an earlier node in the list, creating a closed loop. Detecting these cycles is important because they can cause infinite loops in your programs, leading to crashes or unexpected behavior.

How to Detect Cycles?

We'll explore two efficient methods:

1. Using a HashSet (Hash Table)
2. Floyd's Tortoise and Hare Algorithm

Approach 1: HashSet Method

This approach uses a HashSet (or a similar data structure like a set in Python) to keep track of the nodes we've visited. As we traverse the list, we add each node to the set. If we encounter a node that's already in the set, we know we've found a cycle!

Algorithm:

1. Create an empty HashSet.
2. Start at the head of the list.
3. Check if the current node is in the HashSet:
• If it is, a cycle exists.
• If it isn't, add the node to the HashSet and move to the next node.
4. Repeat until the end of the list or a cycle is detected.

Python Code Example:

 def has_cycle_hashset(head):
  visited = set()
  current = head
  while current:
  if current in visited:
  return True
  visited.add(current)
  current = current.next
  return False
 

Time Complexity: O(n) - We visit each node once.

Space Complexity: O(n) - In the worst case, we store all nodes in the HashSet.

Approach 2: Floyd's Tortoise and Hare

This clever algorithm uses two pointers: a "tortoise" (slow pointer) and a "hare" (fast pointer). The tortoise moves one node at a time, while the hare moves two nodes at a time. If there's a cycle, the hare will eventually lap the tortoise.

Algorithm:

1. Initialize slow and fast pointers to the head.
2. Move slow one step and fast two steps at a time.
3. If they meet, a cycle exists.
4. If the fast pointer reaches the end (null), there's no cycle.

Python Code Example:

 def has_cycle_tortoise_hare(head):
  slow = fast = head
  while fast and fast.next:
  slow = slow.next
  fast = fast.next.next
  if slow == fast:
  return True
  return False
 

Time Complexity: O(n) - We might traverse the list at most twice.

Space Complexity: O(1) - We use only two pointers.

Comparing the Approaches

Here's a summary:

Method	Time Complexity	Space Complexity
HashSet	O(n)	O(n)
Tortoise and Hare	O(n)	O(1)

Floyd's algorithm is generally preferred because of its constant space complexity. The HashSet method is easier to understand but can be less efficient for very large lists.

Conclusion

We've covered two effective ways to detect cycles in linked lists: using a HashSet and Floyd's Tortoise and Hare algorithm. Floyd's algorithm shines with its space efficiency. Understanding these techniques is crucial for building robust and efficient data structures and algorithms. Try implementing them yourself to solidify your understanding!