Find start node of loop in linkedlist in java

Table of Contents [hide]

Java Linked List Interview Programs:
- - Algorithm:
  - Java code :

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.

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 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);
    }
}

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

5 6 7 1 2

start Node of loop is 7

Please go through java interview programs for more such programs.

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

Find start node of loop in linkedlist in java

Java Linked List Interview Programs:

Algorithm:

Java code :

Was this post helpful?

Author

Leave a Reply Cancel reply

Categories

Popular Posts

Let’s be Friends

Java Linked List Interview Programs:

Algorithm:

Java code :

Was this post helpful?

Related posts:

Share this

Author

Leave a Reply Cancel reply

Let’s be Friends