142. 环形链表 II.md

date created	date modified
2022-09-13, 21:47:14	2022-09-13, 21:47:17

Meta

• alias:
• parent :: [[algo-数学]]，[[algo-快慢指针]]
• siblings ::
• child ::
• refs: https://leetcode.cn/problems/linked-list-cycle-ii/

---

代码整体思路：

1. 先判断链表是否有环
2. 如果有环，再找环入口

关键思路：

1. 利用快慢指针是否相遇判断链表是否存在环
2. fast、slow 相遇时，用新指针 p 指向 head 节点，slow 和 p 同时出发，当 slow 和 p 相遇时即环入口
   1. slow 一定在第一圈还没走完时就会被 fast 追上（可证）

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 当快慢指针在环中相遇时，快指针走过的路程为：a+b+kn
        // 慢指针走过的距离为：a+b
        // a 表示起点到环入口距离，b 表示相遇点到环入口距离，k 表示圈数，n 表示一圈长度
        // (a+b)/1 = (a+b+kn)/2 ===> a = kn-b
        // 如何理解 kn-b？kn 表示 k 圈，-b 表示少走 b 的距离，即环入口点
        // 两个相同速度的指针同时出发，一个从起点出发，一个从相遇点出发，两者最终会在环入口处相遇

        // 先通过快慢指针判断链表是否有环
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        // 到达此行可能为无环终止，也可能为相遇 break
        if (fast == null || fast.next == null) return null;
        // 相遇 break
        ListNode p = fast; // 新指针 p 从相遇点出发
        slow = head; // slow 重新从起点出发
        while (p != slow) {
            p = p.next;
            slow = slow.next;
        }
        // 同时到达环入口
        return p;
    }
}