У овом примеру ћемо научити да откријемо да ли постоји петља у ЛинкедЛист-у на Јави.
Да бисте разумели овај пример, требало би да имате знање о следећим темама програмирања Јава:
- Јава ЛинкедЛист
- Јава методе
Пример: Откривање петље на повезаној листи
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."); ) ) )
Оутпут
ЛинкедЛист: 1 2 3 4 Постоји петља у ЛинкедЛист-у.
У горњем примеру смо у Јава имплементирали ЛинкедЛист. Користили смо Флоидов алгоритам за проналажење циклуса да бисмо проверили да ли постоји петља у ЛинкедЛист-у.
Примети код унутар checkLoop()методе. Овде имамо две променљиве именоване прву и другу које прелазе чворове у LinkedList.
- прво - прелазак са 2 чвора у једној итерацији
- друго - прелазак са 1 чвором у једној итерацији
Два чвора се крећу различитим брзинама. Стога ће се састати ако постоји петља LinkedList.
