In a couple of previous Posts, We already went through the Singly Linked List Problem statements:
Implementing a Circular Singly Linked List in Java ?
How to check whether a linked list has a loop/cycle in java ?
In this post, We will learn How to find start a node of loop in Singly LinkedList in java?
The logic used in this Program:
- First of all, we have to find a meeting point of slowReference and fastReference.
- Next Step to set slowReference to head node of LinkedList.
- Afterward move slowReference and fastReference both by one node at a time
- The node at which slowReference and fastReference meets that will be starting node of the loop.
Below is the complete source code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
package com.kkjavatutorials.util; /** * Find start node of loop in Singly LinkedList in java ? * @author KK JavaTutorials */ public class LinkedList<T> { private Node<T> head; //This internal class represents Node in Linked List private static class Node<T>{ private T data; private Node<T> next; public Node(T data) { super(); this.data = data; this.next = null; } } /** * This method insert a Node in Linked List * @param newNode has to insert in the List */ public void insert(Node<T> newNode) { if(head == null) { head = newNode; }else { Node<T> currentNode = head; while (currentNode.next != null) { currentNode = currentNode.next; } currentNode.next = newNode; } } /** * Method to find start node of loop in * Singly LinkedList in java * @return Start node of loop in LinkedList */ public Node<T> findStartNodeOfTheLoop() { boolean isLoop = false; Node<T> fastReference = head; Node<T> slowReference = head; while (fastReference != null && fastReference.next != null) { fastReference = fastReference.next.next; slowReference = slowReference.next; if (slowReference == fastReference) { isLoop = true; break; } } if (isLoop) { slowReference = head; while (slowReference != fastReference) { slowReference = slowReference.next; fastReference = fastReference.next; } } else { slowReference = null; } return slowReference; } public static void main(String[] args) { Node<Integer> node1 = new Node<Integer>(10); Node<Integer> node2 = new Node<Integer>(20); Node<Integer> node3 = new Node<Integer>(30); Node<Integer> node4 = new Node<Integer>(40); Node<Integer> node5 = new Node<Integer>(50); Node<Integer> node6 = new Node<Integer>(60); Node<Integer> node7 = new Node<Integer>(70); LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.insert(node1); linkedList.insert(node2); linkedList.insert(node3); //Node with value 40 added first time linkedList.insert(node4); linkedList.insert(node5); linkedList.insert(node6); linkedList.insert(node7); //Node with value 40 added Second time linkedList.insert(node4); Node<Integer> loopNode = linkedList.findStartNodeOfTheLoop(); if(loopNode != null) { System.out.println("Start node of loop in Singly LinkedList = "+loopNode.data); }else { System.out.println("Loop does not exists in Linked List!!"); } } } |
Output of this Program:
Start node of loop in Singly LinkedList = 40
You May Also Like:
- How to remove a given key from the Singly Linked List in Java ?
- How to remove a node from a Singly Linked List at a given position in Java?
- How to remove the last node from a Singly Linked List in Java
- How to remove the first node from a Singly Linked List in Java ?
That’s all about Find start node of loop in Singly LinkedList in java?
If you have any feedback or suggestion please feel free to drop in below comment box.