题解 | #判断链表中是否有环#

import java.util.*;
/**
 * 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) {
        // 左程云老师讲过类似的题，那道题是这道题的进阶问题，要求返回成环的结点
        // 采用快慢指针，快指针一次走两个结点，慢指针一次走一个结点，若二者能相遇，则有环，否则无环

        // 补充：若要求返回成环（相交）结点，那么在快慢指针相遇之后，令快指针返回head，降速成一次走一个结点
        // 当二者再次相遇的结点就是成环结点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.先判断链表为空的情况
        if (head == null) {
            return false;
        }
        // 2.确定链表不为空
        ListNode fast = head;
        ListNode slow = head;

        do {
            // 3.如果链表是无环的，那么fast一定先走到null，直接return false即可
            if (fast.next == null || fast.next.next == null) {
                // 这里一定不会报空指针异常，因为先判断fast.next == null，若满足，则直接return false，不会继续判断后面
                return false;
            }
            // 4.快指针一次走两个结点，慢指针一次走一个结点
            fast = fast.next.next;
            slow = slow.next;
        } while(fast != slow);
        // 5.若因为fast == slow而结束循环，说明fast和slow二者相遇了，说明链表有环
        return true;
    }
}