共计 506 个字符，预计需要花费 2 分钟才能阅读完成。
如下图, 单链表中存在环:
怎么判断单链表中存在环呢? 先创造一下带环的单链表:
代码如下:
创建带环单链表:
结果可见:
判断单链表是否带环, 以下有三种方法: 第一种方法, 创建哈希表, 不过会占用较大的空间, 不是最佳方法.(时间复杂度 O(n) )
遍历链表, 将链表各节点添加至哈希表中, 添加前判断此节点是否已存在哈希表中, 存在的话说明链表中存在环.
结果如下:
检测到节点 B 是重复项, 说明存在环
第二种方法: 给节点添加 visited 访问标记 (时间复杂度 O(n)), 不需要额外的空间
遍历链表, 每访问一个新节点, 使其 visited 为 1, 每次访问节点前先判断其 visited 是否为 1, 为 1 则是已访问过的节点, 说明链表中存在环.
结果可见:
遍历链表前, 链表每个节点 visited 都为 0, 都没被访问过 B 节点的 visited 为 1, 说明已访问过 B, 链表中存在环遍历后, 链表中每个节点 visited 都为 1, 每个节点都被访问过
第三种方法: 快慢指针法, 设定快指针 fast, 慢指针 slow, 每次循环快指针 fast 移动两个位置, 慢指针移动一个位置 (时间复杂度 O(n)) 需要额外的空间
结果可见:
快指针 fast 和慢指针 slow 在节点 D 相遇, 说明链表中存在环
原理如下图:
正文完