链表有环，求环节点的入口

[geosmart]

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。

HashSet求解

• 时间复杂度：O(n)

  • 空间复杂度：O(n)

  /**

  • 求链表中环的入口节点
  • 用Set 保存已经访问过的节点，遍历整个列表并返回第一个出现重复的节点。
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  • @param head 链表头节点
  • @return 是否循环链表 */ public static ListNode detectCycle(ListNode head) { Set nodes = new HashSet<>(); while (head != null) { if (nodes.contains(head)) { return head; } nodes.add(head); head = head.next; } return null; }

Floyd算法求解

Floyd判圈算法，也称龟兔赛跑算法，可用于判断链表、迭代函数、有限状态机是否有环。如果有，找出环的起点和大小。时间复杂度O(n)，空间复杂度O(1)。

求解原理

假设相遇于 D 点，则快指针应该这时刚好套慢指针一圈（ 2 倍速的必然结果，可以数学证明）， 则此时快指针走的路程为 AB + BCDEB + BD （用 BCDEB 表示一圈）(字母序表示方向，AB 表示 A -> B)

• 慢指针走的路程为 AB + BD； 由于 SS(快指针) = 2 * S(慢指针) （因为 2 倍速）（ SS 表示总路程），
• AB + BCDEB + BD = 2 * (AB + BD) -----(1)
• AB + BD = BCDEB -----(2) 上式表明此时慢指针走过的全部路径刚好一圈，我们的目标是获得 BB 点这一入环点，又根据一圈的关系，有一圈剩余部分，
• DB = BCDEB - BD -----(3) 联立式(2)(3)，有
• AB = DB -----(4) 上式表示 DD 到 BB 的距离和 AA 到 BB 的距离是相等的

  在慢指针从相遇点 DD 继续向前走 DBDB 个长度，一个新指针从 AA 起始点用同样速度。 开始走，两个指针将会在 BB 点相遇，而 BB 点也正是我们想要的相遇点。

代码

    /**
     * Floyd求链表中环的入口节点
     * 1.定义快慢指针求相遇点，快指针比慢指针快2倍；
     * 2.在相遇点，定义1个指针从头，1个指针从相遇点，一起开始逐步前进，下次相遇点即为环入口；
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @param head 链表头节点
     * @return 是否循环链表
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        //寻找相遇
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //寻找环入口
        ListNode meetSlow = head;
        while (meetSlow != fast) {
            fast = fast.next;
            meetSlow = meetSlow.next;
        }
        return meetSlow;
    }