In dit voorbeeld zullen we leren detecteren of er een lus is in LinkedList in Java.
Om dit voorbeeld te begrijpen, moet u kennis hebben van de volgende Java-programmeeronderwerpen:
- Java LinkedList
- Java-methoden
Voorbeeld: lus detecteren in een LinkedList
class 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("There is a loop in LinkedList."); ) else ( System.out.println("There is no loop in LinkedList."); ) ) )
Uitvoer
LinkedList: 1 2 3 4 Er is een lus in LinkedList.
In het bovenstaande voorbeeld hebben we een LinkedList in Java geïmplementeerd. We hebben Floyds cycluszoekalgoritme gebruikt om te controleren of er een lus in LinkedList zit.
Let op de code in de checkLoop()methode. Hier hebben we twee variabelen met de naam eerste en tweede die de knooppunten doorkruisen LinkedList.
- eerste - verplaatsing met 2 knooppunten in enkele iteratie
- tweede - traverse met 1 knoop bij enkele iteratie
Twee knooppunten doorkruisen met verschillende snelheden. Daarom zullen ze elkaar ontmoeten als er een lus is LinkedList.
