问跟踪链表中的检测循环
EN

Stack Overflow用户

提问于 2016-04-25 14:55:32

回答 1查看 34关注 0票数 0

因此，关于如何检测链表中的循环有几个问题。Here就是一个例子。我的问题是，为什么所有这些算法都使用两个指针？你就不能用一个指针循环一遍并将节点标记为已访问的节点，当您到达已经访问过的节点或到达链接列表的末尾(next = null)时，您就知道没有循环了吗？

回答已采纳

发布于 2016-04-25 14:58:07

这是因为

标记访问的节点

您要么需要节点本身的额外空间来完成，要么需要一个辅助数据结构，它的大小将随着列表的大小而增加，而两个指针解决方案只需要足够的额外空间来多一个指针。

编辑：.也许也是因为双指针解决方案很聪明，而且人们喜欢用聪明的方法解决问题。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/36844136

复制

相似问题

问跟踪链表中的检测循环EN