How to detect a loop in a linked list

Detecting a loop

A loop in a linked list can be detected in multiple ways. We may either use a dictionary or a map to detect a loop. We can also detect a loop using Floyd's Cycle-Detection Algorithm.

Floyd's cycle detection algorithm

In this algorithm, we use two pointers that traverse through the list. One moves one step at a time while the other moves two steps at a time. If we encounter the end of the list, there is no loop, but if the two pointers meet at some node, there is a loop in the list.

Code

class LinkedList:
  def __init__(self):
    self.root = None
  def detectLoop(self):
    slow = self.root
    fast = self.root
    while fast.after and fast.after.after:
      fast = fast.after.after
      slow = slow.after
      if slow == fast:
        return True
    return False
my_list1 = LinkedList()
my_list1.root = Node(3)
my_list1.root.after = Node(9)
my_list1.root.after.after = Node(13)
my_list1.root.after.after.after = Node(12)
my_list1.root.after.after.after.after = Node(8)
my_list1.root.after.after.after.after.after = Node(15)
my_list1.root.after.after.after.after.after.after = my_list1.root.after.after
print("List 1", "has" if my_list1.detectLoop() else "does not have", "a loop.")
my_list2 = LinkedList()
my_list2.root = Node(7)
my_list2.root.after = Node(3)
my_list2.root.after.after = Node(8)
print("List 2", "has" if my_list2.detectLoop() else "does not have", "a loop.")

Explanation

Lines 5–13: Two variables slow and fast iterate through the list. The variable fast moves two steps while slow moves one step. If they point at the same node at any point, there is a loop. Otherwise, if they reach None, there is no loop in the list.
Lines 15–29: We create two linked lists, one with a loop and the other without one, and call the detectLoop() function on them.

Using a dictionary

We can also use a dictionary to detect a loop in a linked list. We can do this by adding the nodes as keys in a dictionary. Should we encounter a key twice, we would know that the list contains a loop.

Code

class LinkedList:
  def __init__(self):
    self.root = None
  def detectLoop(self):
    visited_nodes = dict()
    curr = self.root
    visited_nodes[curr] = True
    while curr.after:
      try:
        if visited_nodes[curr.after]:
          return True
      except:
        visited_nodes[curr.after] = True
        curr = curr.after
    return False
my_list1 = LinkedList()
my_list1.root = Node(3)
my_list1.root.after = Node(9)
my_list1.root.after.after = Node(13)
my_list1.root.after.after.after = Node(12)
my_list1.root.after.after.after.after = Node(8)
my_list1.root.after.after.after.after.after = Node(15)
my_list1.root.after.after.after.after.after.after = my_list1.root.after.after
print("List 1", "has" if my_list1.detectLoop() else "does not have", "a loop.")
my_list2 = LinkedList()
my_list2.root = Node(7)
my_list2.root.after = Node(3)
my_list2.root.after.after = Node(8)
print("List 2", "has" if my_list2.detectLoop() else "does not have", "a loop.")

Explanation

Lines 6–8: We create a dictionary that stores the addresses of nodes we have already visited and sets the value to True.
Lines 10–12: The try block checks if a node already exists in visited_nodes and returns True.
Lines 13–15: The except block adds a node to the dictionary and updates the value of curr to move through the list.
Line 16: If the while loop encounters a None node, it exits the loop, and the function returns True.
Lines 18–32: We create two linked lists and call the function detectLoop(), which checks if there's a loop in the linked list.

Note: You can read about removing a loop in a linked list here.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

How to detect a loop in a linked list

Loop in a linked list

Detecting a loop

Floyd's cycle detection algorithm

Code

Explanation

Using a dictionary

Code

Explanation