当前位置：首页 > article >正文

Leetcode 环形链表

article 2024/11/13 1:41:17

在这里插入图片描述

java 代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //初始特殊情况判断，如果链表为空或只有1个节点，返回false
        if(head == null || head.next == null) {
            return false;
        }
        //初始化快慢指针
        ListNode slow = head;
        ListNode fast = head.next;

        while(slow != fast) {
            //因为 fast 每次移动两步，因此如果链表长度是奇数，fast 最终会变为 null；
            // 如果链表长度是偶数，fast 的 next 会变为 null。这两种情况都表示链表已经走到尽头，不存在环。
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

代码片段中，判断条件 fast == null || fast.next == null 是为了处理链表没有环的情况，以及避免访问空指针的错误。具体原因如下：

1. 检测链表末尾：

当链表没有环时，fast 指针会逐步移动到链表的末尾。此时，fast 会指向 null，表示链表已经结束。
因为 fast 每次移动两步，因此如果链表长度是奇数，fast 最终会变为 null；如果链表长度是偶数，fast 的 next 会变为 null。这两种情况都表示链表已经走到尽头，不存在环。

2. 避免空指针异常：

在 Java 中，如果访问一个 null 对象的属性或调用它的方法（比如 fast.next），会引发 NullPointerException 错误。因此在访问 fast.next 之前，必须先确保 fast 本身不是 null。
通过 fast == null || fast.next == null 这个判断，可以避免指针越界的错误。当 fast 或者 fast.next 为 null 时，说明链表已经到达末尾，没有环。

3. 为何返回 `false`：

如果 fast 到达了链表的末尾（null），意味着链表是有尽头的，并且不存在环。因此直接返回 false，表示链表中没有环。

代码逻辑总结：

fast == null：表示链表长度是奇数，fast 指针走到了链表的最后一个节点。
fast.next == null：表示链表长度是偶数，fast 指针走到了倒数第二个节点，再往前走就越界了。

因此，if (fast == null || fast.next == null) 这段判断逻辑是为了及时检测链表是否结束，以及避免空指针访问错误。如果链表没有环，fast 会在遍历过程中变为 null 或其 next 变为 null，此时直接返回 false，表明链表中没有环。

查看全文

http://www.kler.cn/a/319453.html