An interesting algorithm used to detect cycles in linked lists. Well, it really isn't limited to that but used primarily for the cycle detection.
Today was my first step back into DSA after the holidays, and this was the first problem I encountered. Without going much into the details of the question, I'll tell you what it was.
So basically a linked list was provided to me and it asked to check if the list contained a cycle. If yes return 1 else 0
Initially I wasn't aware of this algorithm so as anyone would, I used an old school approach where I maintained track of the visited nodes. If the already visited nodes came while traversing the list then i would return 1 else 0.
Coding implementation
def has_cycle(head):
visited = []
current = head
while current is not None:
if current in visited:
return 1
visited.append(current)
current = current.next
return 0
Well this was fine and all but after submitting my solution when I looked at the discussion section. I saw people talking about this algorithm. Then, After some research I got the hang of it.
Here, we maintain two pointers a slow and a fast pointer. Slow pointer metaphorically is the tortoise which moves one step at a time and the fast pointer metaphorically the hare is the one which moves two step at a time.
We exit the loop if our hare reaches the end, it signifies that no loop was present else its impossible for the hare to reach the end.
In case there is a point where hare and tortoise come back together even though their speed differs then it signifies that there was a loop which sent hare back.
Coding implementation
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return 1
return 0
If you want to try out the question yourself, Here is the link: Cycle-Detection
You might wonder except for cycle detection where else can it be used. Here are some use cases where you'll find this algorithm to be a life savior:
Finding Middle Element of the list
Finding the Start of a cycle
Finding repeated pattern in sequences
Optimizing iterative process
Want to learn more about how we can use this algorithm for these cases? Let's connect!
Top comments (1)