题目
给你一个链表的头节点 head ,判断链表中是否有环
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环
如果链表中存在环 ,则返回 true 。 否则,返回 false
链表类
答题处
规则示例
规则
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
示例1:
输入:head = [3,2,0,-4]
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
示例2:
输入:head = [1,2]
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
示例3:
输入:head = [1]
输出:false
解释:链表中没有环。
解题分析一:判断重复
这道题最简单的做法就是在遍历链表的同时记录下每一个节点,在遍历过程中不停的判断当前节点是不是之前已经记录过的节点。
如果遍历时发现有和记录下来的节点重复的,则证明是环形链表;
如果整个链表能够遍历完也没有重复节点,则证明不是环形链表。
这里的重复不是指 值的重复,而是引用地址指向的重复
解题一:判断重复
解题分析二:快慢指针
快慢指针算法,一般指Floyd判圈算法(Floyd Cycle Detection Algorithm),又称龟兔赛跑算法(Tortoise and Hare Algorithm),是一个可以在有限状态机、迭代函数或者链表上判断是否存在环,以及判断环的起点与长度的算法。
简单原理就是用两个指针,一个快,一个慢。
快指针一次移动两步;慢指针一次移动一步。如果存在环,那么快指针始终可以追上慢指针,即两个指针一定会出现指向同一个节点的状态,就好像赛跑中被套圈。
解题二:快慢指针
总结
快慢指针相对判断重复,空间复杂度更低,他们的时间复杂度相同。在完成该题时,建议大家使用Floyd判圈算法(龟兔赛跑算法)。
END