Find start node of loop in linkedlist in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

In this post, we will see how to find start node of loop in linkedlist in java. We have already seen how to detect a loop in linkedlist in java. This is extension of that post.

Java Linked List Interview Programs:

Algorithm:

It is quite easy to find starting node of loop in linkedlist.

  • Find meeting point of slowPointer and fastPointer.
  • set slowPointer to head node of linkedlist.
  • Move slowPointer and fastPointer both by one node.
  • The node at which slowPointer and fastPointer meets, will be starting node of loop.
You must be wondering how above approach will work.
Lets understand with help of example:
As per above diagram:

Find first node
Distance travelled by slowPointer= A+B
Distance travelled by fastPointer= (A+B+C) + B =A+2B+C
Let speed of slow pointer be X , so speed of fast pointer will be 2*X
As per simple distance speed, time relation:
(A+B)/X=A+2B+C/2*X
2*(A+B)=A+2B+C
2A+2B=A+2B+C
A=C
Hence if we set slowPointer to head and move both slowPointer and fastpointer by one node, they will meet at start node of loop.

Java code :

When you run above program, you will get following output:
Please go through java interview programs for more such programs.

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *