解题思路

本题就是一个经典的快慢指针案例，关于快慢指针可以看：https://leetcode.cn/leetbook/read/linked-list/jcp57/

参考幻灯片，点击后可以使用键盘上下键↕控制：

动图：


tips：

关于为什么在slow.next 与 fast 相遇时不会判定为相遇呢，因为代码我设置的是在fast.next.next之后才进行判断是否相等的，因此可以保证fast至少经历过1轮环的。

实现代码

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

这样还可以进一步优化，fast完全可以直接使用head

/**
 * 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) {
        ListNode slow = head;
        while (head != null && head.next != null) {
            slow = slow.next;
            head = head.next.next;
            if (slow == head) return true;
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：O(n)

  • 空间复杂度：O(1)