查找链表是否为循环列表

Question

很抱歉再次提出基本问题，但我正在寻找答案。对于这个问题，为什么应该有快速和慢速指针迭代列表？为什么它不应该是一个具有以下逻辑的单个指针

ptr = head->next;
while(ptr != NULL)
{
    if(ptr == head)
    {
        return true;
    }
    ptr = ptr->next;
}
return false;

为什么不能是这个逻辑？所有答案都基于两个指针逻辑，这样做有什么好处吗？

Answer 1

您不必有两个指针。 例如，您可以保留一个已经看到的指针列表或表，然后有一个指针遍历该列表并查阅该表以查看它是否已看到该列表。

与表查找解决方案相比，双指针解决方案的优势在于，无论列表有多大，您都只需为两个指针分配额外的内存。

你不能做一个指针并检查头部，除非你只关心有一个循环回到头的列表。 该列表可以在中间的某个地方循环回。

Answer 2

如果您的列表中有一个不包含头部的循环，并且您只有一个指针，您将如何识别它？你将永远陷入循环。
您需要两个指针（或先前节点的列表或类似的东西）来解决此问题。

Answer 3

以下是查找循环的几种方法。

http://ostermiller.org/find_loop_singly_linked_list.html

Answer 4

bool circular(node head*){
    //Honestly not sure if this should be true or false...
    if(head->next == NULL) return false; 
    node ptr = head->next;
    while(ptr != NULL)
    {
        if(ptr == head)
        {
            return true;
        }
        ptr = ptr->next;
    }
    return false;
}

你确实需要 2 个指针...头部和PTR。

您需要跟踪 head 的位置，并且还需要另一个指针来遍历列表。

此外，通过您的实现，它将始终返回 true，因为ptr == head.

编辑：

阅读您的链接。

您还需要检查其他节点（不仅仅是头部）是否是圆形的

通读此链接，它很好地分解了它。

http://umairsaeed.com/2011/06/23/finding-the-start-of-a-loop-in-a-circular-linked-list/