Give a list of distinct nodes in a singly linked list, we want to check if a there is a cycle in it.
Example:
Input: 1→3→5→6→7
Output: No cycle detected
Input: 1→3→5→6→7→9→2→5. Here assume that the last node(5) is same as the middle node(5) and everything repeats after that as depicted in the picture above.
Output: Cycle detected
Solution:
To solve this problem we need to visualize it as a real world example. If indeed a cycle exists then we can visualize this like fast runners overlap other relatively slow runners in a track field running computation. Therefore, we can use two runners (pointers) for our linked list and we deliberately make one slow by moving the cursor one node at a time but the other one fast by moving it two nodes at a time. As a result these two runner eventually overlap each other and hence bingo we know that there is a cycle in the linked list.
bool hasCycle(SinglyLinkedListNode head) {
SinglyLinkedListNode slow = head;
SinglyLinkedListNode fast = head;
while(fast!=null && fast.next !=null) {
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;//cycle exists
}
return false;
}