Algorithm|LinkedList
快慢指针
判断环
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
第一思路:存储访问Map
第一眼想到的是用一个Map存储是否已经访问的状态
在一次遍历的过程中更新这个Map
如果存在环,那么一定会再次访问Map中相同的节点,这个时候就可以以此来进行判断了
1 |
|
进阶思路:快慢指针
这是经典的Floyd判圈算法,原理很简单:我们手动设定两个指针,一快一慢,如果存在环,那么一定会有某个时刻,快的重新追上慢的
原理虽然简单,但是带来的效果很强大,他解决了我们第一种情况下O(n)空间复杂度的问题,只实现了常量级(O(2))的内存,就实现了一样的效果
1 |
|
Algorithm|LinkedList
http://example.com/2025/07/18/Algorithm-LinkedList/