Finding loop in Linked List

Problem Statement

You are given a singly linked list which may or may not contain a loop. The task at hand is to find if the loop exists.  Here is a diagrammatic representation of a loop in a singly linked list.

Finding loop in LinkedList
Finding loop in LinkedList

It is pretty clear that there is a loop which starts at the node 3 and there are 10 nodes which make the loop. In this case we need to print a YES. If it had been a singly linked list without the node 12 connecting to node 3, we would have printed a NO.

Approach to Finding loop in Linked List

The logic here is pretty simple, but first let me show you the mechanics behind the logic.

lldiagram

In the above circle, there are seven stations and you there are to robots stationed at any one station (let say 7). Suppose one of the robot moves slow and the other one moves with twice the speed of the slow robot. Here the blue represents the fast robot (FP) and the green represents the slower robot (SP).

The steps taken by SP  advances it by one station at a time, where as the steps taken by FP advances it by two station at the same time. It means that the SP is going to take 7 steps to reach its initial position, where as the FP will cross its initially position in 4 steps and repeat the stations again to reach station 7 in seven steps only.

Which is an axiom. In a circle if two pointers start from a given point and one of them is twice the speed of other, they will always meet at the starting point after the slower pointer completes one rotation.

Another way of understanding it is our friend Physics. The relative speed by which the Faster pointer moves is Speed (FP) – SPeed(SP) = 2-1 = 1.

Now the distance which it needs to cover before before meeting SP is 7 stations. Hence, it needs to take seven steps at the relative speed which is always one.

This also means that, if two pointers are moving in a circle at a speed ratio of 2:1 , they will definitely meet at some place. This is the knowledge we will apply for our problem at hand.

Source Code

Analysis

There is absolutely no space required, except for holding two pointers. Hence, we can safely assume O(1) constant space.

The time complexity will be proportional to N because the faster pointer will cover twice the distance to move the slower pointer. And the slower pointer traverses the linked list exactly once. Hence, we can safely say O(N) for the time complexity.