牛客网高频算法题系列-BM6-判断链表中是否有环题目描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

原题目见：判断链表中是否有环_牛客题霸_牛客网

解法一：双指针法

使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

原理可参考：双指针算法原理详解

解法二：哈希法

使用HashSet记录链表中的结点，然后遍历链表结点：

如果链表中的结点在哈希表中出现过，说明链表有环，直接返回true

如果链表中的结点没有在哈希表中出现过，则将当前结点添加到哈希表中，然后判断下一个结点

最后，如果没有重复节点，则说明无环，返回false。

代码

import java.util.HashSet;public class Bm006 {    /**     * 双指针     *     * @param head     * @return     */    public static boolean hasCycle(ListNode head) {        ListNode fast = head, slow = head;        while (fast != null && fast.next != null) {            // 快指针每次走2步，慢指针每次走1步            fast = fast.next.next;            slow = slow.next;            if (fast == slow) {                // 快慢指针相遇，说明链表中有环                return true;            }        }        // 快慢指针没有相遇，说明无环        return false;    }    /**     * 哈希法     *     * @param head     * @return     */    public static boolean hasCycle2(ListNode head) {        // 用来记录链表中未重复的结点        HashSet<ListNode> nodes = new HashSet<>();        while (head != null) {            // 如果链表中的结点已经出现过，说明有环，返回true            if (nodes.contains(head)) {                return true;            }            nodes.add(head);            head = head.next;        }        // 如果没有重复节点，则说明无环，返回false。        return false;    }    public static void main(String[] args) {        /**         * 测试用例链表结构为有环         * testCaseCycle：  3 -> 2 -> 0 -> -4         *                      ^          |         *                      ------------         */        ListNode head = ListNode.testCaseCycle();        /**         * 测试用例，期望输出： true         */        System.out.println(hasCycle(head));        System.out.println(hasCycle2(head));    }}

1.01^{365} ≈ 37.7834343329 0.99^{365} ≈ 0.02551796445 相信坚持的力量！