Bad*_*adr 3 c c++ loops linked-list
可能重复:
如何确定链接列表是否仅使用两个内存位置进行循环.
你好我在接受采访时被问到如何只使用两个指针在链接列表中找到一个循环.
我做了以下事情:
1)每次找到链接列表的中心
2)通过在末尾迭代这两个指针,如果没有指向同一节点并且找到null,那么指针将指向同一节点,那么链接列表中没有循环.
有没有有效的方法来做到这一点......？
提前.
我想你正在寻找Floyd的循环检测算法,也称为"Tortoise和Hare算法".我们的想法是将一个指针("乌龟")设置为列表中的第一个节点,将另一个指针("野兔")设置为下一个项目.然后在每一步中,"乌龟"指针前进一个位置,"野兔"前进两步.在每次迭代之后,检查指针以查看它们是否指向同一节点.如果发生这种情况,该节点必须是循环的一部分.
要找到循环的开始,将两个指针中的一个重新定位到列表的开头,而另一个指针保留在其当前位置.然后两个指针都被提前,这次指针每次迭代只需一步,直到它们再次相遇.该(第二)汇合点是循环中的第一个节点.