[LeetCode Hot 100] LeetCode141. 环形链表

题目描述

思路：快慢指针

• slow指针：每次移动一个节点
• fast指针：每次移动两个节点
• 如果链表中存在环，fast指针最终会在某一时刻追上slow指针，这是由于移动速度快的fast指针会在某个时刻绕圈并追上速度慢的slow指针
• 条件 fast != null && fast.next != null 保证了在每一步迭代中，fast 和 fast.next 都不为 null。这样做有两个目的：
  1. 防止在访问fast.next时出现 NullPointerException，因为如果 fast 或 fast.next 是 null，说明链表已经遍历结束，不存在环。
  2. 通过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有意义。