代码随想录-链表-环形链表

142 环形链表2

思考：

1. 如何判断链表存在环？

• 快慢指针，两指针分别以不同速度前进，若存在环则理应相遇。
  1. 如何设置速度，确保存在环的情况下快慢指针一定相遇？
  • 慢指针步长为1，快指针呢？若存在环，一定是f先进入环随后绕环，带s进入环后f以(stepF-stepS)的速度追赶s，因此stepF=2时，每过一个时刻f都接近s一步，这样就能保证两者一定能在环中相遇。

2. 如何找到环的入口？
   1. 为什么s不会在绕环若干圈后相遇？
   2. 蓝色波浪线的等式说明什么？
   • 首先n>=1，即相遇前f至少绕环1周过了；
   • 当n=1时，x=z，表明此时(f与s第一次相遇时)若p、q同时出发（步长为1），那么x步后两者会相遇；
   • 当n>1时，表明q在遇到p之前会线绕环(n-1)圈；
   • 最重要的是，p、q第一次相遇的结点真是环的入口！

代码：

ListNode fast = head, slow = head, target = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                while (target != slow) {
                    target = target.next;
                    slow = slow.next;
                }
                return target;
            }
        }
        return null;

---

本文章使用limfx的vscode插件快速发布