Question
141. 环形链表
难度：简单
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
Solution
双指针法我们已经做过很多题，其中有一道移动零不知道大家还记得吗？
快慢指针, 快指针每次比慢多走一个, 如果追上慢指针说明有环。
还有一个问题就是如何确定边界值：
如果是环形链表，快慢指针就一定会有相遇的时候
如果不是环形链表，快慢指针的next就一定会有为空的时候。
这样，无论是否是环形链表，都可以跳出循环。
Code
所有leetcode代码已同步至github
欢迎star
/** * @author yitiaoIT */ class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } }
Result
复杂度分析
- 时间复杂度：O(N)
🌈寻宝
⭐今天是坚持刷题更文的第16/100天
⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
⭐更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找，寻宝游戏现在开始。
找不到可以评论留言，一条就会注意到你。
如果还不行，请私信我。
