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

import java.util.HashSet;

/**
 * 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) {
        //方法一：利用集合元素的唯一性，运行时间大概是90ms
//        //特殊值处理,链表为空
//        if(head == null){
//            return false;
//        }
//        ListNode head0 = head;
//        //创建一个哈希集合，存储对象为ListNode
//        HashSet<ListNode> hashSet = new HashSet<>();
//        //遍历链表，如果在哈希集合中存在该节点，即链表存在环；否则，将该节点添加到哈希集合中
//        while (head0 != null){
//            if(hashSet.contains(head0)){//哈希集合中存在该节点
//                return true;
//            }else{//哈希集合中不存在该节点，将该节点添加到哈希集合中
//                hashSet.add(head0);
//            }
//            head0 = head0.next; //节点移动
//        }
//        return false;

        //方法二：利用快慢指针，运行时间大概是60ms
        //特殊值处理,链表为空或者链表的长度为1
        if(head == null || head.next == null){
            return false;
        }
        ListNode fast = head.next.next;  //初始化快指针
        ListNode flow = head.next;  //初始化慢指针
        while (flow != null && fast != null){  //遍历链表，当快慢指针都不为空时，
            if(flow == fast){//如果快慢指针指向同一个节点，则代表有环
                return true;
            }else{//如果快慢指针不是指向同一个节点,更新快慢指针
                flow = flow.next;  //慢指针每次走一步
                fast = fast.next;  //快指针每次走两步
                if(fast != null){//快指针每次走两步，可能存在刚走完一步就是空指针，所以要验证快指针为非空
                    fast = fast.next;
                }
            }
        }
        return false;
    }
}