循环链表算法

Question

我最近在求职面试中被问到开发一种算法,可以确定链表是否是周期性的.由于它是一个链表,我们不知道它的大小.这是一个双向链表,每个节点都有"下一个"和"前一个"指针.节点可以连接到任何其他节点,也可以连接到自身.

我当时提出的唯一解决方案是选择一个节点并与链表的所有节点一起检查.面试官显然不喜欢这个想法,因为它不是最佳解决方案.什么是更好的方法？

Answer 1

您正在寻找的是一种循环寻找算法.Joel所指的算法被称为'乌龟和野兔'算法或Floyd的循环发现算法.我更喜欢第二种,因为它听起来像是一个很好的D&D咒语.

Wikpedia概述循环查找算法,带有示例代码

Answer 2

一般的解决方案是让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