如何判断给定的单链表是否是循环？
我在一次采访中被问到单链表是否有循环。我搜索了这个SO并找到了几个答案面试问题：如何检测链接列表中的循环？并且我之前就知道这些答案，但不知何故我的回答与我在讨论中想到的不同很久以前和朋友讨论过，但不确定答案是否正确。如果我自己尝试一下，它会按预期工作。不知何故，面试官不高兴。有人可以澄清这有什么问题吗？
struct node {
int flag;
struct node *next;
}
我的想法不是使用两个指针并进行不同的跳跃，而是使用单个指针并遍历每个节点，例如：
node = node->next;
我要做的就是在每次遍历节点并每次检查时将标志变量设置为 1 例如
if (node->flag)
{
return TRUE; // implies list is a loop
}
else{
node->flag = 1;
}
除了效率之外，这种方法有什么问题吗？
I was asked in an interview to find if the single linked list has a loop. I have searched this SO and found few answers Interview question: How to detect a loop in a linked list? and I knew about those answers before but somehow I answered it different which I had in mind from my discussion with friends long time back, but I wasn't sure if the answer is correct. If try it myself it works as expected. Somehow the interviewer is not happy. Can someone clarify what is wrong in this ?
struct node {
int flag;
struct node *next;
}
My idea here is not to use two pointers and hop variantly but to use single pointer and traverse each node e.g:
node = node->next;
Only this I would do is set the flag variable to 1 when ever I traverse the node and check each time e.g
if (node->flag)
{
return TRUE; // implies list is a loop
}
else{
node->flag = 1;
}
Other than efficiency, what is wrong in this approach ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您需要为每个列表项存储额外的数据（
flag）。因此，您的方法需要 O(N) 额外内存，而使用两个指针的方法仅需要 O(1) 内存。所以你的方法内存效率不高。
You need additional data (
flag) to store for each list item. So your approach needs O(N) additional memory, while approach with two pointers needs only O(1) memory.So you approach is not memory efficient.
您的方法甚至更有效，但依赖于您可以修改列表表示的事实。当被问到同样的问题时，我给出了相同的解决方案，但面试官告诉我，我不允许以任何方式修改列表。
Your approach is even more efficient but relies on the fact that you may modify the list representation. When asked the same question I gave the same solution but the interviewer told me I am not allowed to modify the list in any way.
您正在使用一个额外的整数变量
flag，并假设您机器中的sizeof(int)是4个字节，并且假设链表中有100,000个节点，那么您最终将多使用 400,000 字节。这大约是 390M/.38G要重置链表中所有节点的
flag，即使是 O(n)，您也必须遍历所有 100,000 个节点。这是一个开销。现在，如果您将基于
flag的解决方案与 2 变量解决方案进行比较，那么计算时间几乎相同，但 2 变量解决方案被认为非常内存高效，因为它不使用 390M 内存来识别循环！You are using an extra integer variable
flagand say if thesizeof(int)in your machine is 4 bytes and say you have 100,000 nodes in the linked-list, then you will end up using 400,000 bytes more. That will be approximately 390M/.38GTo reset the
flagfor all the nodes in the linked-list, even though it is O(n), you'll have to traverse all the 100,000 nodes. Its an overhead.Now, if you compare your
flagbased solution with the 2-variable solution, then it is almost the same computational time but 2-variable solution is considered very memory efficient as it does not use 390M of memory to identify the loop!你的答案没有错，它不是使用两个指针，而是只使用一个指针。但给出这个面试问题的答案你忽略了一个基本前提。
除非绝对必要，否则您通常不应该更改所给问题的数据结构。从这个角度考虑。
如果它不是链接列表，而是公司开发的应用程序，并且他们需要您查明某个特定事物是否适合该应用程序，该怎么办？在这种情况下，他们不希望您更改应用程序代码（因为除非不可避免，否则这是不切实际的），但希望您使用已有的代码。
因此，你的面试官对这个答案并不满意。除了其他答案之外，您始终可以给出此答案，但不能作为您选择的答案。
Your answer is not wrong, rather instead of using two pointers, it makes use of just one pointer. But giving this answer for the interview question you over looking one basic premise.
You are generally not supposed to alter the data structure of the problem which you are given until it is absolutely necessary to do so. Consider it from this point of view.
What if it's not a linked list but an application that the company has developed and they need you to find out if a particular thing stands true for that application or not. In this case they don't expect you to change the application code(as that is impractical unless unavoidable) but would like you to work around with what you have got.
Because of this your interviewer was not happy with the answer. You can always give this answer in addition to the other answer, but not as your answer of choice.
也许
兔子和乌龟会起作用。Turtle通常在列表中进行交互，一次一项，而Hare的速度是前者的两倍，一次两项。如果野兔超过了乌龟，则存在一个循环。编辑：我看到此建议已在此处，并且已被拒绝OP，在他的评论中。
Perhaps
Hare and Turtlewould work. TheTurtleinterates through the list normally, one item at a time, while theHaregoes twice as fast, two items at a time. If theHarepasses theTurtle, there is a loop.Edit: I see this suggestion is already here, and that it has already been rejected by the OP, in his comments.