检测链接列表中的循环 [英] Detecting loop in a Linked List

问题描述

如何使用单个指针检测链表中的循环？ （不想要慢和快的指针（野兔和龟））

How to detect loop in a linked list using only single pointer? (Don't want slow and fast pointers(Hare and Tortoise))

推荐答案

布伦特算法在这里显然是最好的：对于无循环的列表，只需访问列表一次，而Floyd的乌龟和野兔需要重新访问一半的节点。对于具有循环的列表，循环中它不会比Floyd旋转更长;而在最好的情况下只需要一个周期，当Floyd需要很多时。想到一个长无循环的序列，然后是一个长度为1的循环。在这种情况下，Brent的最佳情况是在循环访问后检测循环 - 因此访问每个节点一次;而Floyd必须平均访问每个节点三次。

Brent's algorithm is clearly the best here: For loop-free lists it simply visits the list once while Floyd's tortoise and hare requires to revisit half of the nodes. For lists with loops it never "rotates" longer in the loop than Floyd ; and in the best case needs only one cycle, when Floyd needs many. Think of a long loop-free sequence followed by a loop of lenght 1. In this case, the best case for Brent would be to detect the cycle after one visit of the loop - so visiting each node exactly once ; whereas Floyd has to visit each node on average three times.

基本思想是访问链表，并将当前节点的指针与一个已经访问的节点进行比较。也就是说，每个访问节点的一个指针比较。指针根据简单的逻辑不时更新。

The basic idea is to visit the linked list and compare the pointer of the current node with one already visited node. That is, one pointer comparison per visited node. The pointer is updated from time-to-time following a simple logic.

这篇关于检测链接列表中的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！