2023年7月29日每日一题--141. 环形链表

leetcode链接：141. 环形链表

题目分析

快慢指针。

方案一

public class Solution {
    public boolean hasCycle(ListNode head) {

        if (head == null) return false;
        ListNode slow = head,  fast = head;

        do {
            if (fast.next == null || fast.next.next == null)
                return false;
            slow = slow.next;
            fast = fast.next.next;
        } while (fast != slow);

        return true;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:42.4 MB,击败了60.78% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

官方题解

https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/

方法一：哈希表

此处再具体介绍

方法二：快慢指针

public 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;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

此题是关于环形链表的相关内容，相对简单，如果想进阶的话，可以做一下 142. 环形链表 II

个人博客参考：

https://www.yuanql.top/2023/06/08/02_leetcode/142.%20%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8%20II/
https://www.yuanql.top/2023/07/15/02_1_%E4%BB%A3%E7%A0%81%E9%9A%8F%E6%83%B3%E5%BD%95%E7%AE%97%E6%B3%95%E8%AE%AD%E7%BB%83%E8%90%A518%E6%9C%9F/04%E3%80%81%E7%AC%AC%E4%BA%8C%E7%AB%A0%20%E9%93%BE%E8%A1%A8part02/#142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II%E2%80%BB