可能重复:
查找链接列表中是否存在没有两个指针的循环
如何确定链接列表是否只使用两个内存位置进行循环.
测试链表是否有循环的最佳算法
在准备面试时,我遇到了以下问题:
如何使用额外的空间复杂度O(1)来确定链接列表(任何类型)是否包含循环？您不能假设循环从第一个节点开始(当然,循环不必包含所有节点).
我找不到答案,虽然我觉得这很简单......
dty*_*dty 11
简单.保持两个指向列表的指针.在每个步骤中,通过单个链接前进一个指针,并通过两个链接前进另一个指针.测试它们是否指向相同的元素.如果是这样,你就有一个循环.如果没有,请重复,直到找到循环或到达列表末尾.
| 归档时间： |
|
| 查看次数： |
4594 次 |
| 最近记录： |