如何通过示例检测Java中链表中的循环

高效的方法：

解决这个问题的有效方法是弗洛伊德的循环检测算法，因此该算法的步骤是：

使用两个指针 fastPtr 和 SlowPtr 并将两者初始化为链表的头部
每次迭代中将 fastPtr 移动 2 个节点，将 SlowPtr 移动 1 个节点。
如果 fastPtr 和 SlowPtr 在某个迭代中相遇，则链表中存在循环。
如果 fastPtr 到达链表末尾而没有遇到慢指针，则链表中不存在循环（即 fastPtr->next 或 fastPtr->next->next 变为 null）

该算法的 Java 代码为

public boolean ifLoopExists() {
  Node fastPtr = head;
  Node slowPtr = head;
  while (fastPtr != null && fastPtr.next != null) {
   fastPtr = fastPtr.next.next;
   slowPtr = slowPtr.next;
   if (slowPtr == fastPtr)
    return true;

  }
  return false;
 }

上述解决方案的时间复杂度为 o(n)，空间复杂度为 o(1)。

让我们创建没有循环的链表：

让我们创建一个名为“LinkedList.java”的 java 程序

package org.arpit.java2blog;

public class LinkedList{

    private Node head;

    private static class Node {
        private int value;
        private Node next;

        Node(int value) {
            this.value = value;

        }
    }

    public void addToTheLast(Node node) {

        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;

            temp.next = node;
        }
    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }

    public boolean ifLoopExists() {
        Node fastPtr = head;
        Node slowPtr = head;
        while (fastPtr != null && fastPtr.next != null) {
            fastPtr = fastPtr.next.next;
            slowPtr = slowPtr.next;
            if (slowPtr == fastPtr)
                return true;

        }
        return false;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Creating a linked list

        list.addToTheLast(new Node(5));
        list.addToTheLast(new Node(6));
        list.addToTheLast(new Node(7));
        list.addToTheLast(new Node(1));
        list.addToTheLast(new Node(2));

        list.printList();

        // Test if loop existed or not
        System.out.println("Loop existed-->" + list.ifLoopExists());

    }
}

从逻辑上讲，我们的链表可以表示为：

运行上面的程序，你将得到以下输出：

5 6 7 1 2
Loop existed-->false

让我们在链表中创建一个循环

现在我们将最后一个节点连接到值为 7 的节点，它将在链表中创建循环，因此将上面的 main 方法更改为：

public static void main(String[] args) {
        LinkedList list = new LinkedList();
        // Creating a linked list
        Node loopNode=new Node(7);
        list.addToTheLast(new Node(5));
        list.addToTheLast(new Node(6));
        list.addToTheLast(loopNode);
        list.addToTheLast(new Node(1));
        list.addToTheLast(new Node(2));

        list.printList();
        // creating a loop
        list.addToTheLast(loopNode);
        // Test if loop existed or not
        System.out.println("Loop existed-->" + list.ifLoopExists());

    }

运行上面的程序，你将得到以下输出：

5 6 7 1 2
Loop existed-->true

这就是检测链表中循环的方法。

原文链接：codingdict.net

如何通过示例检测Java中链表中的循环

高效的方法：

让我们创建没有循环的链表：

让我们在链表中创建一个循环

热门标签