我看不出有任何方法可以让这花费固定的时间或空间，两者都会随着列表的大小而增加。

我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前，您可以对其调用containsKey。如果节点已经存在，则有一个周期。

ItentityHashMap使用==而不是.equals，这样你就可以检查对象在内存中的位置，而不是它是否具有相同的内容。

比弗洛伊德的算法好

Richard Brent描述了一种替代周期检测算法，它很像兔子和乌龟(弗洛伊德周期)，除了这里的慢节点不移动，但随后会以固定的间隔“传送”到快节点的位置。

该描述可在布伦特的周期检测算法(瞬移海龟)。布伦特声称他的算法比弗洛伊德的循环算法快24%到36%。 O(n)时间复杂度，O(1)空间复杂度。

public static boolean hasLoop(Node root) {
    if (root == null) return false;
    
    Node slow = root, fast = root;
    int taken = 0, limit = 2;
    
    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if (slow == fast) return true;
        
        if (taken == limit) {
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

乌龟和兔子

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

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

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

我可能会非常晚和新的处理这个线程。但还是. .

为什么不能将节点的地址和“下一个”节点指向存储在表中

如果我们可以这样做

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

这样就形成了一个循环。

//链表查找循环函数

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

你可以使用弗洛伊德的周期寻找算法，也被称为乌龟和野兔算法。 其思想是对列表有两个引用，并以不同的速度移动它们。一个向前移动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;
    }
}