假设您在Java中有一个链表结构。它由节点组成:

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

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

你可以使用弗洛伊德的周期寻找算法,也被称为乌龟和野兔算法。 其思想是对列表有两个引用,并以不同的速度移动它们。一个向前移动1个节点,另一个向前移动2个节点。

如果链表有一个循环 一定会见面的。 或者 这两个引用(或下一个) 将变为null。

实现算法的Java函数:

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;
    }
}

其他回答

您甚至可以在常数O(1)时间内完成(尽管它不是非常快或有效):计算机内存可以容纳的节点数量是有限的,比如N条记录。如果遍历超过N条记录,那么就有一个循环。

//链表查找循环函数

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

乌龟和兔子

看看波拉德的算法。这不是完全相同的问题,但也许你会理解其中的逻辑,并将其应用于链表。

(如果你很懒,你可以看看周期检测——看看关于乌龟和兔子的那部分。)

这只需要线性时间和2个额外的指针。

在Java中:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

(大多数解决方案不会同时检查next和next。接下来是null。此外,因为乌龟总是在后面,你不需要检查它是否为空——兔子已经检查过了。)

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

请原谅我的无知(我对Java和编程仍然相当陌生),但为什么上面的方法不能工作呢?

I guess this doesn't solve the constant space issue... but it does at least get there in a reasonable time, correct? It will only take the space of the linked list plus the space of a set with n elements (where n is the number of elements in the linked list, or the number of elements until it reaches a loop). And for time, worst-case analysis, I think, would suggest O(nlog(n)). SortedSet look-ups for contains() are log(n) (check the javadoc, but I'm pretty sure TreeSet's underlying structure is TreeMap, whose in turn is a red-black tree), and in the worst case (no loops, or loop at very end), it will have to do n look-ups.

我不确定这个答案是否适用于Java,但我仍然认为它属于这里:

当我们在现代体系结构中使用指针时,我们可以期望它们是CPU字对齐的。对于64位体系结构,这意味着指针的前3位始终为零。这让我们可以使用这个内存来标记我们已经见过的指针,通过对它们的第一个比特写入1。

如果我们遇到一个指针,它的第一个位已经写了1,那么我们已经成功地找到了一个循环,之后我们需要再次遍历结构,并将这些位屏蔽掉。完成了!

这种方法被称为指针标记,它在低级编程中被过度使用,例如Haskell在一些优化中使用它。