Overview : A Linked List is considered to have a loop or a cycle , if a node is visited more than once while traversing the list.
Problem :
Given a singly linked list , detect wether it has a loop or not . Note that the head pointer may be 'null' if the list is empty.
( Problem Source : Cracking the coding interview : HackerRank)
Solution :
The solution is based on floyd's cycle finding algorithm , also referred to as the 'Tortoise and Hare' algorithm. It uses two pointers , which move at different speeds. Let us call them as slow and fast pointers. Now the fast pointer can move at any speed which should be greater than slow pointer's speed. Simple mathematics* suggests that if we move the fast pointer with speed twice that of slow , and if they meet , the linked list has a cycle .
*Why fast = slow * 2 ?
Below is the java code for the logic .
