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

Trong bài viết này, chúng ta sẽ hiểu cách phát hiện vòng lặp trong LinkedList. Danh sách liên kết (linked list) là chuỗi các cấu trúc dữ liệu, được kết nối với nhau qua các liên kết (links). Linked List là chuỗi các liên kết chứa các mục. Mỗi liên kết chứa kết nối đến liên kết khác.

Minh họa dưới đây:

Giả sử đầu vào là:

Run the program

Đầu ra mong muốn:

The loop exists in the linked list

Thuật toán

Bước 1 - BẮT ĐẦU 
Bước 2 - Khai báo biến 
Bước 3 - Định nghĩa giá trị 
Bước 4 - Định nghĩa class với các thành viên liên quan 
Bước 5 - Tạo instance của class, khởi tạo các node 
Bước 6 - Định nghĩa hàm kiểm tra vòng lặp 
Bước 7 - Tạo HashSet, thêm phần tử vào node đầu tiên 
Bước 8 - Trỏ node đến phần tử tiếp theo sau mỗi lần lặp 
Bước 9 - Trong main, tạo instance và thêm phần tử vào list bằng 'push' 
Bước 10 - Gọi phương thức 'check_loop', hiển thị thông báo 
Bước 11 - DỪNG

Ví dụ 1

Ở đây, chúng ta dùng phương pháp duyệt (traversal) để tìm vòng lặp.

import java.util.*; 

public class Demo { 
    static Node head; 
    static class Node { 
        int data; 
        Node next; 
        Node(int d){ 
            data = d; 
            next = null; 
        } 
    } 
    
    static public void push(int new_data){ 
        Node new_node = new Node(new_data); 
        new_node.next = head; 
        head = new_node; 
    } 
    
    static boolean check_loop(Node head){ 
        HashSet s = new HashSet(); 
        while (head != null) { 
            if (s.contains(head)) 
                return true; 
            s.add(head); 
            head = head.next; 
        } 
        return false; 
    } 
    
    public static void main(String[] args){ 
        System.out.println("The required packages have been imported"); 
        Demo input_list = new Demo(); 
        input_list.push(45); 
        input_list.push(60); 
        input_list.push(75); 
        input_list.push(90); 
        input_list.head.next.next.next.next = input_list.head; 
        if (check_loop(head)) 
            System.out.println("The loop exists in the linked list"); 
        else 
            System.out.println("The loop doesnot exists in the linked list"); 
    } 
}

Kết quả

The required packages have been imported 
The loop exists in the linked list

Ví dụ 2

Ở đây, chúng ta đóng gói các thao tác vào các hàm thể hiện lập trình hướng đối tượng (sử dụng thuật toán Floyd's Cycle Detection - con trỏ nhanh/chậm).

public class Demo { 
    Node head; 
    static class Node { 
        int value; 
        Node next; 
        Node(int d) { 
            value = d; 
            next = null; 
        } 
    } 
    
    public boolean check_loop() { 
        Node first_node = head; 
        Node second_node = head; 
        while(first_node != null && first_node.next != null) { 
            first_node = first_node.next.next; 
            second_node = second_node.next; 
            if(first_node == second_node) { 
                return true; 
            } 
        } 
        return false; 
    } 
    
    public static void main(String[] args) { 
        Demo input_list = new Demo(); 
        input_list.head = new Node(45); 
        Node second_node = new Node(60); 
        Node third_node = new Node(75); 
        Node fourth_node = new Node(90); 
        input_list.head.next = second_node; 
        second_node.next = third_node; 
        third_node.next = fourth_node; 
        fourth_node.next = second_node; 
        System.out.print("The elements of the linked list are: "); 
        int i = 1; 
        while (i <= 4) { 
            System.out.print(input_list.head.value + " "); 
            input_list.head = input_list.head.next; 
            i++; 
        } 
        boolean loop = input_list.check_loop(); 
        if(loop) { 
            System.out.println("\nThere is a loop in the linked list."); 
        } else { 
            System.out.println("\nThere is no loop in the linked list."); 
        } 
    } 
}

Kết quả

The required packages have been imported 
The loop exists in the linked list