How to find the length of a loop in a linked list

Loop in a linked list

A linked list is a commonly used data structure made up of nodes that are interlinked using pointers.

Note: Read more on a linked list here.

A linked list may contain a loop if a node points to another node that comes earlier in the chain. If this happens, an endless loop is created in the linked list.

class LinkedList:
  def __init__(self):
    self.root = None
  def findLoopLength(self):
    slow = self.root
    fast = self.root
    while fast.after and fast.after.after:
      fast = fast.after.after
      slow = slow.after
      if slow == fast: # check if the two pointers match to find loop point
        count = 1
        curr = slow.after
        while curr != slow: # move through the linked list and keep counting
          curr = curr.after
          count += 1
        return count
    # if no loop found return 0
    return 0
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("The length of the loop in list 1 is:", my_list1.findLoopLength())
my_list2 = LinkedList()
my_list2.root = Node(7)
my_list2.root.after = Node(3)
my_list2.root.after.after = Node(8)
print("The length of the loop in list 2 is:", my_list2.findLoopLength())

Explanation

Lines 5–11: Two variables, fast and slow, go through the list and find the point of the loop by following Floyd's cycle detection algorithm.
Lines 12–17: We create another variable curr that starts at the loop point and goes through the list, counting the number of nodes till it reaches the loop point again. We then return the number of nodes in a variable count.
Lines 15–29: We create two linked lists, one having a loop and the other without a loop, and then call the function findLoopLength to find the length of the loop.

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

How to find the length of a loop in a linked list

Loop in a linked list

Finding the length of a loop

Code

Explanation