gpt4 book ai didi

c - 检测链表中的多个循环

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:47:59 25 4
gpt4 key购买 nike

我想在以下情况下检测循环

1-2-3-4-5
|----------| ===> case 1

1-2-3-4-5
|-------| ===> case 2

在案例 1 中,循环检测算法工作正常,但在案例 2 中却没有。我对案例 2 进行了试运行,我发现 hare 指针正常结束。我还认为案例 2 不是有效的单链表,因为它包含 2 个下一个指针。我的假设对案例 2 是否正确?整个场景是针对单链表的?

最佳答案

这是一个不涉及分配堆内存的循环检测解决方案:

struct Node {
int val;
struct node * next;
};

bool containsCycle(Node * head)
{
Node * walker = head;
NOde * fastWalker = head;
while(walker && fastWalker)
{
fastWalker = fastWalker->next;
if(walker == fastWalker)
return true;
if(fastWalker)
fastWalker = fastWalker->next;
if(walker == fastWalker)
return true;
walker = walker->next;
}
// Fell out of the loop, no cycle
return false;
}

该算法使用两个以不同速度前进的指针。如果列表中存在循环,则其中两个指针将在一点上彼此相等。

关于c - 检测链表中的多个循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11875659/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com