In this post, We will write a java program to check whether a linked list has a loop/cycle in java?
If there is a loop in a linked list that means one of the node refers back to any of the previous nodes rather than referencing the next node to null. If we traverse a linked list with loop will cycle back to the old node rather than concluding its traversal once null is reached causing an infinite loop.
Steps for checking whether LinkedList has loop or cycle is not are as follows-
- We use 2 references(slowReference & fastReference ) which are initialized to the head of the linked list.
- slowReference hop a node and the fastReference takes two hops in each iteration.
- If both of these references point to the same node at some iteration that means there is a loop.
- If any of these references reach null that means there is no loop in the linked list.
|
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 |
package com.kkjavatutorials.util; /** * How to check whether a linked list has a loop/cycle in java * @author KK JavaTutorials * */ public class LinkedList<T> { private Node<T> head; //This inner class represent 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; } } //Method to insert Node in Linked List public void insert(Node<T> newNode) { if(isEmpty()) { head = newNode; }else { Node<T> current = head; while(current.next !=null) { current = current.next; } current.next = newNode; } } //Check if Linked is empty private boolean isEmpty() { return head == null; } //Method to display linked List public void displayLinkedList() { Node<T> current = head; while(current !=null) { System.out.print(current.data+"->"); current = current.next; } } //Method to check whether LinkedList has loop/cycle or not public boolean isCyclicLinkedList() { Node<T> slowReference = head; Node<T> fastReference = head; while (slowReference != null && fastReference !=null && fastReference.next != null) { fastReference = fastReference.next.next; slowReference = slowReference.next; if(slowReference == fastReference) return true; } return false; } public static void main(String[] args) { Node<Integer> node = new Node<Integer>(40); LinkedList<Integer> linkedList = new LinkedList<>(); linkedList.insert(new Node<Integer>(10)); linkedList.insert(new Node<Integer>(20)); linkedList.insert(new Node<Integer>(30)); linkedList.insert(node); linkedList.insert(new Node<Integer>(50)); linkedList.insert(new Node<Integer>(60)); linkedList.insert(new Node<Integer>(70)); linkedList.insert(node); //linkedList.displayLinkedList(); boolean cyclicLinkedList = linkedList.isCyclicLinkedList(); System.out.println(cyclicLinkedList); } } |
Output of above Program:
true
This output shows the Linked list has a loop or cycle.
NOTE:After uncommenting //linkedList.displayLinkedList(); if you run above program then you will get output as below:
10->20->30->40->50->60->70->40->50->60->70->40->50->60->70->40->50->60->70->40->50->60->70->40->50…………………………………..
This output shows that Linked List has a loop or Cycle.
Another approach:
we can take a HashSet where we add each traversed node of the linked list to the HashSet, if the same node is encountered again while adding then we will return true indicating a loop or cycle. But this approach requires extra space as another data structure HashSet is used.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public boolean isCycleLinkedList2() { Set<Node<T>> set = new HashSet<>(); Node<T> currentNode = head; while(currentNode!= null) { if(!set.add(currentNode)) { return true; } currentNode = currentNode.next; } return false; } |
You May Also Like:
Java program to add two matrices
Java program to find maximum element in each row of the matrix
Java program to find maximum and minimum numbers in the given matrix
That’s all about How to check whether a linked list has a loop/cycle in java ?
If you have any feedback or suggestion please feel free to drop in below comment box.