Loop through linked list Java
Ngày đăng:
19/12/2021
Trả lời:
0
Lượt xem:
111
Java Program to Detect loop in a LinkedListIn this example, we will learn to detect whether there is a loop in LinkedList in Java. To understand this example, you should have the knowledge of the following Java programming topics:
Example: Detect Loop in a LinkedListclass LinkedList { // create an object of Node class // represent the head of the linked list Node head; // static inner class static class Node { int value; // connect each node to next node Node next; Node(int d) { value = d; next = null; } } // check if loop is present public boolean checkLoop() { // create two references at start of LinkedList Node first = head; Node second = head; while(first != null && first.next !=null) { // move first reference by 2 nodes first = first.next.next; // move second reference by 1 node second = second.next; // if two references meet // then there is a loop if(first == second) { return true; } } return false; } public static void main(String[] args) { // create an object of LinkedList LinkedList linkedList = new LinkedList(); // assign values to each linked list node linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); // connect each node of linked list to next node linkedList.head.next = second; second.next = third; third.next = fourth; // make loop in LinkedList fourth.next = second; // printing node-value System.out.print("LinkedList: "); int i = 1; while (i <= 4) { System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; i++; } // call method to check loop boolean loop = linkedList.checkLoop(); if(loop) { System.out.println("\nThere is a loop in LinkedList."); } else { System.out.println("\nThere is no loop in LinkedList."); } } }Output In the above example, we have implemented a LinkedList in Java. We have used Floyd's cycle finding algorithm to check if there is a loop in LinkedList. Notice the code inside the checkLoop() method. Here, we have two variables named first and second that traverse the nodes in LinkedList.
Two nodes are traversing at different speeds. Hence, they will meet if there is a loop in LinkedList. |