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

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

如果我们可以这样做

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)

这样就形成了一个循环。

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

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

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

如果链表结构实现了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;
}

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

使用上述函数在java中检测linkedlist中的循环。

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

我读了一些答案，人们忽略了上述问题的一个明显的解决方案。

如果给定我们可以改变类Node的结构，那么我们可以添加一个布尔标志来知道它是否被访问过。这样我们只遍历列表一次。

Class Node{

 Data data;
 Node next;
 boolean isVisited;

}


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

     Node current = head;


     while(current != null){
      if(current.isVisited) return true;
      current.isVisited = true;
      current = current.next;
     }

    return false;

}