关于java:牛客网高频算法题系列BM6判断链表中是否有环

3次阅读

共计 1202 个字符，预计需要花费 4 分钟才能阅读完成。

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

原题目见：BM6 判断链表中是否有环

应用两个指针，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));
    }
}