Hello friends, in my previous article I have discussed how to find if there is a circular link list present. But that was easy. Here is the more tricky part of the question. How to find the starting node for circular linked list.
In this article I will help you to understand the way to find the starting node of a circular linked list in most easy and concise way.
Find the starting node for circular linked list
Lets take the example of the circular linked list which we solved in the last article. In the article we tried to find if the linked list is circular or not.
Above is the circular linked list. If I go by the logic discussed in the previous article. Both the slow pointer and fast pointer will meet at 19 marked in red.
D is the distance till starting node. In above figure node 12, 13 and 15 are for D.
K is the distance starting with the starting node till the meeting point. Nodes 17 and 19 are included in K.
Now to find the starting point of the circular linked list we should have confirmed that linked list is circular and both the pointers are meeting at some point. And we have to assume that there is a node in the linked list which can be the starting node.
Now as we know that we have two pointers i.e. slow pointer and fast pointer. I will denote them by S and F respectively.
Now to travel to meeting point i.e. 19 in the above linked list, the slow pointer has to move D + K steps. Along with that if the meeting doesn’t happen in the first rotation of the circular linked list. The pointer has to move a number of loops. Lets assume it to be i.
The total distance traveled by S is: D + K + i * n , where s(small) is the
S = D + K + i*s
To understand better the i * n, in our example the the slow pointer would be in its first circular ration when it will meet the fast pointer at 19. That is why we can put i = 0. Hence the total distance covered by slow pointer will be D + K.
Now coming to fast pointer(F). The distance traveled by Fast pointer will be D + K + i * n. Where i is the length of the cycle which is same as slow pointer. And f is the number of cycles made by slow pointer.
F = D + K + i*f
But as we know fast pointer moves twice as fast as slow pointer.
F = 2S
D + K + i*f = 2(D + K + i * s)
D = i(f-2s) – K
or
D + K = i(f – 2s)
The above equation means that if we move D + K from the start i(f-2s) is the meeting point.
And to find the D that is the starting point of the circular linked list, we will fall short of K distance as per below statement if we start from the starting of the linked list.
D = i(f-2s) – K
Code Part to Find the starting node for circular linked list
Since before meeting both the pointers have already traveled the distance K. And now if one pointer start from the start of the linked list and other from the meeting point. Both will meet at the start of the circular linked list.
DeterminIfDoublyLinkedList(nodes[0], ref sn, ref fn)
sn = nodes[0];
while (sn != fn)
{
sn = sn.next;
fn = fn.next;
}The above code is continuation from the previous articles code. After meeting and finding the that linked list is circular. Take one of the pointer to the starting of the linked list. And mode both pointer one by one until they meet.