【算法面试必刷Java版六】判断链表是否有环

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：判断链表是否有环

描述：

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 0 ≤n≤10000，链表中任意节点的值满足 |val|<=100000

要求：空间复杂度 O(1)，时间复杂度 O(n)

思路：快慢指针

我们可以使用快慢指针来判断一条链表中是否存在环，快指针每次走两步，慢指针每次走一步，如果快慢指针都进入环中，每次他们之间的距离都会-1，直到快指针追上慢指针。即如果快慢指针相遇，链表即存在环。

代码：

/**
 * 快慢指针
 */
public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast==slow){
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101