c++ - 循环链表算法

最近有人在求职面试中要求我开发一种算法，该算法可以确定链表是否是周期性的。由于它是一个链表，因此我们不知道它的大小。这是一个双向链接的列表，每个节点都有“下一个”和“上一个”指针。一个节点可以连接到任何其他节点，也可以连接到自身。

当时我想到的唯一解决方案是选择一个节点，然后将其与链表中的所有节点一起检查。面试官显然不喜欢这个主意，因为它不是最佳解决方案。有什么更好的方法？

最佳答案

一般的解决方案是让2个指针以不同的速率移动。如果列表的某些部分是圆形的，则它们最终将相等。与此类似:

 function boolean hasLoop(Node startNode){
   Node slowNode = startNode;
   Node fastNode1 = startNode;
   Node fastNode2 = startNode;

   while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
     if (slowNode == fastNode1 || slowNode == fastNode2)
        return true;

     slowNode = slowNode.next();
   }
   return false;
 }

从这里公然被盗:http://ostermiller.org/find_loop_singly_linked_list.html