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

问题描述

说你在Java中有一个链表结构。它由节点组成：

  class Node {
 Node next; 
 //某些用户数据
} 
  

每个节点指向下一个节点，除了最后一个节点，对于下一个节点为null。说有可能列表可以包含一个循环 - 也就是说，最后一个Node而不是一个null，它有一个引用到它之前的列表中的一个节点。

什么是最好的写作方式

  boolean hasLoop（Node first）
  

如果给定的节点是具有循环的列表中的第一个，那将返回 true ，而 false 否则你如何写这样一来，它需要不断的空间和合理的时间？

这是一个循环的列表的图片： p>

解决方案

您可以使用 Floyd的循环查找算法 ，也被称为乌龟和野兔算法。


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

• 如果链接列表有一个循环，他们将
  将绝对满足


• 否则两个引用的
  中的任何一个（或他们的下一个）
  将成为 null 。

实现算法的Java函数：

  boolean hasLoop（Node first）{
 
 if（first == null）// list does not exist..so no loop both。 
返回false; 
 
节点缓慢，快速; //创建两个引用。 
 
 slow = fast = first; //使两者都参考列表的开头。 
 
 while（true）{
 
 slow = slow.next; // 1跳
 
 if（fast.next！= null）
 fast = fast.next.next; // 2跳。 
 else 
返回false; // next node null =>没有循环。 
 
 if（slow == null || fast == null）//如果要命中null..no循环。 
返回false; 
 
如果（慢==快）//如果两个人见面...我们必须有一个循环。 
返回true; 
} 
} 
  

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.

What's the best way of writing

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:

解决方案

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