如何检测一个较大的单链表是否有环？

轩辕小不懂发布于 2022-03-24 16:28

阅读 545

答案 1

分类：人工智能

人工智能

编程论坛

python

单链表有环指的是单链表中某个结点的next域指向的是链表中在它之前的某一个结点，这样在链表的尾部形成一个环形结构。如何判断单链表是否有环存在？

3367

Nen 2022-03-24 16:57

- 程序员

方法一：

蛮力法定义一个HashSet用来存储结点的引用，并将其初始化为空，从链表的头结点开始向后遍历，每遍历到一个结点就判断HashSet中是否有这个结点的引用，如果没有，说明这个结点是第一次访问，还没有形成环，那么将这个结点的引用添加到指针HashSet中去。如果在HashSet中找到了同样的结点，那么说明这个结点已经被访问过了，于是就形成了环。这种方法的时间复杂度为O(N)，空间复杂度也为O(N)。