Java program to detect loop in a linkedlist
Here's a Java program to detect a loop in a linked list:
refer togi:iftidea.comclass LinkedListNode { int value; LinkedListNode next; LinkedListNode(int value) { this.value = value; this.next = null; } } public class Main { public static boolean hasLoop(LinkedListNode head) { if (head == null) { return false; } LinkedListNode slow = head; LinkedListNode fast = head.next; while (fast != null && fast.next != null) { if (slow == fast) { return true; } slow = slow.next; fast = fast.next.next; } return false; } public static void main(String[] args) { // create a linked list with a loop LinkedListNode head = new LinkedListNode(1); head.next = new LinkedListNode(2); head.next.next = new LinkedListNode(3); head.next.next.next = new LinkedListNode(4); head.next.next.next.next = head.next; boolean hasLoop = hasLoop(head); if (hasLoop) { System.out.println("The linked list contains a loop"); } else { System.out.println("The linked list does not contain a loop"); } } }
This program uses two pointers, one moving at a slower pace than the other, to detect a loop in a linked list. We initialize two pointers slow
and fast
to the head of the linked list, with fast
initially pointing to the second node. We then iterate through the linked list with the slow
pointer moving one node at a time and the fast
pointer moving two nodes at a time. If the slow
and fast
pointers ever point to the same node, then there is a loop in the linked list.
In the main
method, we create a linked list with a loop and then call the hasLoop
method to detect the loop. If the linked list contains a loop, the program will print "The linked list contains a loop". Otherwise, it will print "The linked list does not contain a loop".