如果链表结构实现了java.util.List. list。我们可以使用列表大小来跟踪我们在列表中的位置。

我们可以遍历节点，将当前节点的位置与上一个节点的位置进行比较。如果我们当前的位置超过了上一个位置，我们就检测到列表在某个地方有一个循环。

这种解决方案需要恒定的空间，但随着列表大小的增加，完成所需的时间会线性增加。

class LinkedList implements List {
    Node first;
    int listSize;
    
    @Override
    int size() {
        return listSize;
    }

    [..]

    boolean hasLoop() {
        int lastPosition = size();
        int currentPosition = 1;
        Node next = first;
        while(next != null) {
           if (currentPosition > lastPosition) return true;
           next = next.next;
           currentPosition++;
        }
        return false;
    }
}

或作为一种实用工具:

static boolean hasLoop(int size, Node first) {
    int lastPosition = size;
    int currentPosition = 1;
    Node next = first;
    while(next != null) {
       if (currentPosition > lastPosition) return true;
       next = next.next;
       currentPosition++;
    }
    return false;
}

//链表查找循环函数

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。此外，因为乌龟总是在后面，你不需要检查它是否为空——兔子已经检查过了。)

用户unicornaddict上面有一个很好的算法，但不幸的是，它包含一个错误，用于奇数长度>= 3的非循环列表。问题是，快的可能会在列表结束之前“卡住”，慢的会赶上它，然后就会(错误地)检测到循环。

这是修正后的算法。

static 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 = null;
        else
            fast = fast.next.next; // 2 hops.

        if(fast == null) // if fast 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条记录，那么就有一个循环。

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.