Chương trình Java để phát hiện vòng lặp trong LinkedList

Mục lục

Ví dụ: Phát hiện vòng lặp trong danh sách liên kết

Trong ví dụ này, chúng ta sẽ học cách phát hiện xem có vòng lặp trong LinkedList trong Java hay không.

Để hiểu ví dụ này, bạn nên có kiến thức về các chủ đề lập trình Java sau:

Java LinkedList
Phương thức Java

Ví dụ: Phát hiện vòng lặp trong danh sách liên kết

 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."); ) ) )

Đầu ra

 LinkedList: 1 2 3 4 Có một vòng lặp trong LinkedList.

Trong ví dụ trên, chúng tôi đã triển khai một LinkedList trong Java. Chúng tôi đã sử dụng thuật toán tìm chu trình của Floyd để kiểm tra xem có vòng lặp trong LinkedList hay không.

Lưu ý mã bên trong checkLoop()phương thức. Ở đây, chúng ta có hai biến có tên đầu tiên và thứ hai đi qua các nút trong LinkedList.