Given the reference (pointer) to the head node of a linked list, the task is to detect and delete loop in it.
A linked list can contain a self-loop as well.
Input: 1->2->3->4->5->2
Output: 1->2->3->4->5->null
Solutions
Method 1: Floyd's Cycle-Finding Algorithm
In Floyd's Cycle-Finding Algorithm, we traverse a linked list using two pointers.
Move one pointer(slow) by one and another pointer(fast) by two nodes.
If these pointers meet at the same node, then there is a loop.
If pointers do not meet, then the linked list doesn't have a loop.
After detecting the loop, if we start the slow pointer from the head and move both slow and fast pointers at the same speed until fast don't meet, they would meet at the beginning of the loop.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).