如何检测链表中的循环? [英] 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
}

并且每个节点都指向下一个节点，除了最后一个节点，它的 next 为空.假设列表有可能包含一个循环——即最终的 Node 不是空的，而是引用了列表中在它之前的节点之一.

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)

如果给定的 Node 是带有循环的列表的第一个，哪个将返回 true，否则返回 false?你怎么写才能占用恒定的空间和合理的时间?

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:

推荐答案

您可以使用 弗洛伊德的寻环算法，也称为龟兔赛跑算法.

这个想法是对列表有两个引用，并以不同的速度移动它们.将一个向前移动 1 节点，将另一个向前移动 2 个节点.

You can make use of Floyd's cycle-finding algorithm, also known 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.

• 如果链表有一个循环肯定会见面.
• 或者两个引用(或它们的 next)将变为 null.

• 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屋！