如何检测在一个链表中的循环？ [英] How to detect a loop in a linked list?

问题描述

假设你有一个链表结构中的Java。它是由节点：

Say you have a linked list structure in Java. It's made up of Nodes:

class Node {
    Node next;
    // some user data
}

和每个节点指向下一个节点，除了最后的节点，其具有空的下一个。说存在这样的可能性，该列表可以包含一个环 - 即最终节点，而不是有一个空，有一个参照之前它里面传来列表中的节点之一

and each Node points to the next node, except for the last Node, which has null for next. Say there is a possibility that the list can contain a loop - i.e. the final Node, instead of having a null, has a reference to one of the nodes in the list which came before it.

什么是写的最好的办法

boolean hasLoop(Node first)

这将返回真如果给定的节点是第一个列表的一个循环，而假，否则？你怎么能写这样，它需要的空间一定量和时间的合理量？

which would return true if the given Node is the first of a list with a loop, and false otherwise? How could you write so that it takes a constant amount of space and a reasonable amount of time?

下面是一个什么样一个循环列表看起来像一个画面：

Here's a picture of what a list with a loop looks like:

推荐答案

您可以使用 弗洛伊德的cycle-的寻找算法 ，也知道作为的乌龟和野兔算法的。

 这个想法是有两个引用到列表中，移动它们位于不同的速度。通过移动 1 一个向前节点和其他由 2 节点。

You can make use of Floyd's cycle-finding algorithm, also know as tortoise and hare algorithm.

The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.

• 如果链表有一个循环，他们 会的绝对的满足。
• 否则任 两个引用（或它们的接下来） 将成为空。

• If the linked list has a loop they will definitely meet.
• Else either of the two references(or their next) will become null.

Java函数实现的算法：

Java function implementing the algorithm:

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either.
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list.

    while(true) {

        slow = slow.next;          // 1 hop.

        if(fast.next != null)
            fast = fast.next.next; // 2 hops.
        else
            return false;          // next node null => no loop.

        if(slow == null || fast == null) // if either hits null..no loop.
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop.
            return true;
    }
}

这篇关于如何检测在一个链表中的循环？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！