题目描述
思路：快慢指针
- slow指针：每次移动一个节点
- fast指针：每次移动两个节点
- 如果链表中存在环，fast指针最终会在某一时刻追上slow指针，这是由于移动速度快的fast指针会在某个时刻绕圈并追上速度慢的slow指针
- 条件 fast != null && fast.next != null 保证了在每一步迭代中，fast 和 fast.next 都不为 null。这样做有两个目的：
- 防止在访问fast.next时出现 NullPointerException，因为如果 fast 或 fast.next 是 null，说明链表已经遍历结束，不存在环。
- 通过fast.next != null条件，避免了fast.next.next操作中fast.next为null的情况，因为如果 fast.next是null，则无法再访问 fast.next.next。
方法一：
/**
* 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, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}
}
这里注意一下while的条件。
fast = fast.next.next;
首先fast != null，保证fast.next有意义。
fast.next != null，保证fast.next.next有意义。