⭐ 题目日期：

字节 - 25届秋招一面

🌳 题目描述：

链表判断是否有环，如果有环，返回环的入口

🧗难度系数：

⭐️ ⭐️ ⭐️️ ⭐️

📝思路分析：

• 可以用快慢指针（慢指针走 1 步， 快指针走 2 步）来判断链表中是否有环，如果无环，快指针会到达链表的尾部。如果有环，快指针会追上慢指针。

  如何判断环的入口？

• O 为链表的起点，P 为环的入口，Q 为快慢指针的相遇点。OP = a, PQ = b, QP = c。环内指针走向为顺时针。

  慢指针走的距离：Distance(slow) = OP + PQ = a + b。

  为什么不是 a + b + n(b + c)?

  快慢指针相遇时，慢指针没有走完一圈，因为当慢指针走到P点，假设此时快指针距离慢指针X，X < b + c, 慢指针再走X步，快慢指针相遇。所以慢指针没走完一圈。

  快指针走的距离：Distance(fast) = OP + n(PQ + QP) + PQ = a + n(b + c) + b。

  Distance(fast) = 2 Distance(slow), 得出 a + b = n (b + c), 也就是说慢指针走的距离是环周长的整数倍。

  当快慢指针相聚在Q点的同时让一个新指针从头节点(O点)开始走，由于 a = n (b + c) - b, 则当新指针到达P点时，慢指针也刚好到达P点，即相聚于入口点，

💻代码：

Java

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode cur = head;
                while (cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }

        return null;
    }

🚵🏻复杂度分析：

时间复杂度：O(n), 判断环 slow 走过 a + b 个节点，找入口 cur 走过 a 个节点，总的步数小于 2n

空间复杂度：O(1)

题目链接