返回首页 / 程序员知识/如何判断单链表为有环链表？

如何判断单链表为有环链表？

2023-12-07 收藏 110

　　1、通过遍历实现：从给定链表的第一个节点开始遍历，每遍历至一个节点，都将其和所有的前驱节点进行比对，如果为同一个节点，则表明当前链表中有环；反之，如果遍历至链表最后一个节点，仍未找到相同的节点，则证明该链表中无环。

　　2、时间复杂度为 O(n) 的算法：该算法的实现思想需要借助一个论点，即在一个链表中，如果 2 个指针（假设为 H1 和 H2）都从表头开始遍历链表，其中 H1 每次移动 2 个节点的长度（H1 = H1->next->next）,而 H2 每次移动 1 个节点的长度（H2 = H2->next），如果该链表为有环链表，则 H1、H2 最终必定会相等；反之，如果该链表中无环，则 H1、H2 永远不会相遇。

赞同89
应用指南

猜你喜欢