Today let’s look at a python program that will help us check whether there’s a cycle in a given linked list.
The above example illustrates a cycle in Linked List. The best way to check whether it has a cycle is to have two markers (or runners).
The first runner takes one step at a time. The second one takes two steps at a time. With this setup, if there is a cycle, both runners will come to the same place eventually.
You can imagine this happening for runners running around a lake with one person running slow and the other one running fast. The faster runner will eventually complete a round and pass by the slower runner. If this happens, we know there is a cycle.
The code below does exactly that by using two markers.
# Problem: Finding cycle in linked list
# Logic: Maintain two markers, one that moves 2 steps faster
# If markers meet at the end, there's a cycle
def cycle_check(node):
marker1 = node
marker2 = node
while marker2 != None and marker2.next != None:
marker1 = marker1.next
marker2 = marker2.next.next
if marker2 == marker1:
return True
return False
# Testing the result
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
a.next = b
b.next = c
c.next = d
d.next = c
cycle_check(a)
Since we’re making marker2 take two steps at a time, we want to run the while loop till marker2’s current value and its next value doesn’t equal to None. If it is, we stop and return False.
CS Mumbai 