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:
- How to reverse a linked list in java
- How to reverse a linked list in pairs in java
- How to find middle element of linked list in java
- How to detect a loop in linked list in java
- Find start node of loop in linkedlist
- How to find nth element from end of linked list
- How to check if linked list is palindrome in java
- Add two numbers represented by linked list in java
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.
public Node findStartNodeOfTheLoop() {
Node fastPtr = head;
Node slowPtr = head;
boolean loopExists=false;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (slowPtr == fastPtr)
{
loopExists=true;
break;
}
}
if(loopExists)
{
slowPtr=head;
while(slowPtr!=fastPtr)
{
slowPtr=slowPtr.next;
fastPtr=fastPtr.next;
}
}
else
{
System.out.println("Loop does not exists");
slowPtr=null;
}
return slowPtr;
}
You must be wondering how above approach will work.
Lets understand with help of example:
As per above diagram:
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 :
package org.arpit.java2blog;
public class LinkedList{
private Node head;
private static class Node {
private int value;
private Node next;
Node(int value) {
this.value = value;
}
}
public void addToTheLast(Node node) {
if (head == null) {
head = node;
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
}
public void printList() {
Node temp = head;
while (temp != null) {
System.out.format("%d ", temp.value);
temp = temp.next;
}
System.out.println();
}
public Node findStartNodeOfTheLoop() {
Node fastPtr = head;
Node slowPtr = head;
boolean loopExists=false;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (slowPtr == fastPtr)
{
loopExists=true;
break;
}
}
if(loopExists)
{
slowPtr=head;
while(slowPtr!=fastPtr)
{
slowPtr=slowPtr.next;
fastPtr=fastPtr.next;
}
}
else
{
System.out.println("Loop does not exists");
slowPtr=null;
}
return slowPtr;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
// Creating a linked list
Node loopNode=new Node(7);
list.addToTheLast(new Node(5));
list.addToTheLast(new Node(6));
list.addToTheLast(loopNode);
list.addToTheLast(new Node(1));
list.addToTheLast(new Node(2));
list.printList();
list.addToTheLast(loopNode);
Node startNode=list.findStartNodeOfTheLoop();
if(startNode!=null)
System.out.println("start Node of loop is "+ startNode.value);
}
}
When you run above program, you will get following output:
5 6 7 1 2 start Node of loop is 7
Please go through java interview programs for more such programs.
