Java 程序：检测链表中的循环

原文：https://www.studytonight.com/java-programs/java-program-to-detect-a-loop-in-a-linked-list

在本教程中，我们将看到如何在 java 中检测链表中的循环。LinkedList 是一种线性数据结构，其中元素不存储在连续的位置，每个元素都是一个单独的对象，具有数据部分和地址部分。每个元素都被称为一个节点。由于插入和删除的动态性和容易性，它们比数组更受欢迎。但是在继续之前，如果你不熟悉 java 中链表的概念，那么一定要查看一下 Java 中链表上的文章。

输入:输入链表元素:6 7 8 4 5

输出:环路找到

这可以通过使用以下方法来实现:

方法 1:使用HashSet

方法 2:不使用HashSet

让我们看看这些方法中的每一种，以便更好地理解。

程序 1:检测链表中的循环

在这个程序中，我们将看到如何使用哈希方法检测链表中的循环。

算法:

开始
创建链表。
向列表中添加元素。
使用布尔方法检查循环是否存在。
为此使用HashSet。
逐一遍历列表，并不断将节点地址放入HashSet中。
在任何时候，如果达到 null，则返回 false。
如果下一个当前节点指向 HashSet 中任何先前存储的节点，则返回 true。
显示结果。
停止

让我们看看下面的例子，以更好地理解上述算法。

// Java program to detect loop in a linked list
import java.util.*;
public class LinkedList 
{
    static Node head; // head of list
    /* Linked list Node*/
    static class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    static public void add(int newData)
    {
        Node newNode = new Node(newData);
        newNode.next = head;
        head = newNode;
    }
    static boolean checkLoop(Node n)
    {
        HashSet<Node> hset = new HashSet<Node>();
        while (n != null) {
            if (hset.contains(n))
                return true;
            hset.add(n);
            n = n.next;
        }
        return false;
    }
    //Driver program
    public static void main(String[] args)
    {
        LinkedList ll = new LinkedList();
        ll.add(8);
        ll.add(12);
        ll.add(15);
        ll.add(21);
        ll.head.next.next.next.next = ll.head;
        if (checkLoop(head))
            System.out.println("Loop found");
        else
            System.out.println("No Loop found");
    }
}

找到循环

程序 2:检测链表中的循环

在这个程序中，我们将看到如何检测链表中的循环。

算法:

开始
创建链表。
创建链表。
向列表中添加元素。
使用布尔方法检查循环是否存在。
声明一个临时变量并将其初始化为 0。
遍历链表并继续标记被访问的节点。
如果再次找到一个被访问的节点，那么就会出现一个循环。
显示结果。
停止

让我们看看下面的例子，以更好地理解上述算法。

// Java program to detect loop in a linked list
import java.util.*;
public class Main
{
    static class Node
    {
       int data;
       Node next;
       int temp;
    };
    static Node add(Node newHead, int newData)
    {
        Node newNode = new Node();
        newNode.data = newData;
        newNode.temp = 0;
        newNode.next = newHead;
        newHead = newNode;
        return newHead;
    }
    static boolean detect(Node n)
    {
        while (n != null)
        {
            if (n.temp == 1)
               return true;
            n.temp = 1;
            n = n.next;
        }
        return false;
    }
    // Driver code
    public static void main(String[] args)
    {
        Node head = null;
        head = add(head, 20);
        head = add(head, 4);
        head = add(head, 15);
        head = add(head, 10);
        head.next.next.next.next = head;
        if (detect(head))
           System.out.print("Loop found");
        else
           System.out.print("No Loop found");
    }
}

找到循环