当前位置 博文首页 > 一条IT:【leetcode刷题】16.环形链表——Java版
?欢迎订阅《leetcode》专栏,每日一题,每天进步?
使用快慢指针,若指针相遇则判断有环
——leetcode此题热评
哈喽,大家好,我是一条。
糊涂算法,难得糊涂
难度:简单
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 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 或者链表中的一个 有效索引 。
双指针法我们已经做过很多题,其中有一道移动零不知道大家还记得吗?
快慢指针, 快指针每次比慢多走一个, 如果追上慢指针说明有环。
还有一个问题就是如何确定边界值:
next
就一定会有为空的时候。这样,无论是否是环形链表,都可以跳出循环。
所有
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;
}
}
复杂度分析
- 时间复杂度:O(N)
?今天是坚持刷题更文的第16/100天
?各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
?更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝,礼尚往来,给大家准备了一条多年积累下来的优质资源,包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找,寻宝游戏现在开始。
找不到可以评论留言,一条就会注意到你。
如果还不行,请私信我。