[Java·算法·简单] LeetCode 141. 环形链表 详细解读

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例

示例1

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例3

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示

👉️ 力扣原文

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

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; // 快指针追上慢指针，说明链表中存在环
    }
}

详细解读

这个方法使用了双指针技术来检测链表中是否存在环。下面是对方法的详细解读：

1. 初始条件检查：
   • 方法开始时，首先检查链表是否为空，或者是否只有一个节点。如果链表为空或者只有一个节点，肯定不存在环，因此直接返回 false。
2. 初始化指针：
   • 创建两个指针 slow 和 fast，初始时分别指向链表的头节点 head 和 head.next。
   • 这里快指针 fast 比慢指针 slow 快一步是为了保证在检测环时不会因为快指针提前到达末尾而遗漏环的检测。
3. 循环检测：
   • 使用一个 while 循环，条件是 slow 指针不等于 fast 指针。
   • 在循环中，先检查快指针 fast 是否为 null，如果是，说明已经到达了链表的末尾，即链表中不存在环，直接返回 false。
   • 然后让慢指针 slow 前进一步，即 slow = slow.next。
   • 接着让快指针 fast 前进两步，即 fast = fast.next.next。
   • 循环结束的条件是 slow 和 fast 相遇，即两个指针指向了同一个节点，表示链表中存在环。
4. 返回结果：
   • 如果循环结束时，slow 和 fast 相遇了，说明链表中存在环，返回 true。
   • 如果循环结束时，快指针 fast 到达了链表的末尾，则说明链表中不存在环，返回 false。

这种方法的时间复杂度是 O(n)，其中 n 是链表的节点数，因为在最坏情况下，快指针 fast 最多会遍历整个链表一次。而空间复杂度是 O(1)，因为只使用了常数个额外的指针。