+7 投票
分类:问答挑战 | 用户: 10 9 8 (5.7k 分)

如何判断一个单向链表是否有环?如下图所示

2 个回答

+2 投票
用户: 8 5 3 (2.1k 分)
采纳于 用户:
 
已采纳

哈希表好像还没学。

快指针和慢指针:

设这两个指针都从链表的头节点开始移动,快指针每次移动两步,慢指针每次移动一步。

如果链表中存在环,那么快指针最终一定会追上慢指针,此时可以直接退出循环并返回 True。

否则,如果快指针到达了链表尾部,下一个节点应该为 None ,这个时时如果还没有追上慢指针,则说明链表中没有环。

0 投票
用户: 10 9 8 (5.7k 分)
提示:

可以使用哈希表或快慢指针
欢迎来到 在线问答系统 ,有什么不懂的可以尽管在这里提问,你将会收到社区其他成员的回答。
...