判断链表中是否有环

在这里插入图片描述

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public boolean hasCycle(ListNode head) {
        // 空链表直接无环
        if (head == null) {
            return false;
        }

        // 快慢指针都从表头出发
        ListNode slow = head; 
        ListNode fast = head; 

        
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针走1步
            fast = fast.next.next;  // 快指针走2步

            // 快慢指针相遇 → 链表有环
            if (fast == slow) {
                return true;
            }
        }

        //快指针走到尾部，无环
        return false;
    }

这里说明一下循环条件为什么要这么写：

因为快指针的核心操作是：

1

fast=fast.next.next

这一步其实可以等价拆解为两步的连续next调用：

1
2
3


ListNode temp = fast.next;//取fast的下一个节点

fast = temp.next;//取temp的下一个节点

要让这两步都不触发空指针异常，需要满足以下两个前提：

fast.next不报错，也就是fast不能为null
temp.next不报错，也就是temp不能为null，即fast.next不能为null

因此，循环条件就是：

1

fast!=null&&fast.next!=null