检测链表中的循环

Question

首先，我要提一下，我已经查看并了解了最流行的检测链表是否有循环的算法（谈论这个How to detect a loop in a linked list?）

但是，我尝试实现自己的想法，它似乎适用于我的示例 - 但是它在 http://leetcode.com/ 的执行时间上失败了，这让我觉得它可能会以某种方式进入无限循环。

我的问题是：我需要知道我的代码是否正确，或者在某些情况下确实进入了无限循环。

这是单链表的定义。

class ListNode {
   int val;
   ListNode next;
   ListNode(int x) {
       val = x;
       next = null;
   }
}

这是函数：

public boolean hasCycle(ListNode head) {
    //create a list that will contain the elements that have been visited
    List<ListNode> ref = new ArrayList<ListNode>();

    ListNode element = head;
    //add the first element to the list
    ref.add(head);

    boolean contains = false;

    //the special case when the linkedlist is empty
    if(head==null)
        return false;
    while(contains == false){
        if(element.next!=null && !ref.contains(element.next)){
            ref.add(element.next);
            element = element.next;
            contains = false;
        }
        else if (ref.contains(element.next))
            contains = true;
        else if(element.next == null)
            return false;
    }
    return contains;
}

Answer 1

我认为您的代码不可能进入死循环。遵循算法的可能控制流程：

如果头部为空，return 为假。头部为空现在是不变的。
如果头部的下一个节点是它自己，return false。头部被抢先添加到已访问元素的集合中，使这变得微不足道。
如果当前节点的下一个节点非空且之前没有被访问过，则将其添加到已访问节点列表中并继续执行。
如果当前节点的下一个节点是非空的但之前被访问过，则执行（现在是多余的）检查以确保该节点之前肯定被访问过。在这一点上，我们保证在列表中有一个循环，所以我们 return true.
如果当前节点的下一个节点为null，检查之前是否访问过任何null节点。由于我们的不变量，即 head 一开始就不为空，因此无法到达该特定分支。
执行（现在是多余的）检查以查看当前节点的下一个节点是否为空。在这一点上，当前元素的下一个元素是 null 是有保证的，因此很容易得出这样的结论：当列表被完全遍历时没有遇到循环并且 return false.[=26= 是安全的]

在任何时候都没有导致程序状态不以某种方式前进的分支，可以肯定地说无限循环不是问题。

您算法的真正问题似乎是它的时间复杂度。确保 java.util.ArrayList 不包含特定值需要完全遍历列表并每次都对每个元素调用 Object#equals。如果您坚决反对使用一种更传统的循环节点 link 检查算法，例如您 link 编辑的算法，我绝对建议您使用 java.util.HashSet 来代替这样的算法.它通过设计提供非常快速的查找元素是否存在于其中。

此外，如果您处在不那么做作的情况下，其中有为节点编写的自定义 equals 和 hashCode 方法，您可能不得不求助于通过包装器类和 hashCode 和 equals 来跟踪节点通过 System#identityHashCode 调用代理的方法和 real 节点的引用相等性检查。否则，该算法可能会在实际上不存在循环的情况下确定存在循环。

检测链表中的循环

Detect loop in linked list

java

linked-list

infinite-loop

circular-reference