屏幕快照 2019-05-28 下午10.43.57.png

解釋

6001559055056_.pic.jpg

當我們通過slow和fast碰撞得出他是有環(huán)的，這時候開始節(jié)點到loop的距離x1，等于他們相遇節(jié)點到loop開始的節(jié)點(距離為x3)
我們在開始節(jié)點和相遇節(jié)點，創(chuàng)建兩個節(jié)點，一次走一步，最終會相遇在loop開始的地方
fast跑的距離為：x1+x2+x3+x2+m(x3+x2) m代表跑了多少圈 你也去好奇為什么會額外有個(x2+x3)，因為fast為了跟slow碰撞，他始終要循環(huán)一圈回來碰撞
slow跑的距離為：x1+x2+n(x2+x3) n代表跑了多少圈
fast = 2slow 則 x1+x2+x3+x2+m(x3+x2) = 2(x1+x2+n(x3+x2))
x2+x3 m(x3+x2) = x1+x2+2n(x3+x2)
x3 + ?(x3+x2) = x1 //這里我們不管他跑了多少圈，總之剩下x3和x1的距離到loop開始的點是一樣的，兩邊一起跑就會相遇在該點

public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            Boolean isCircle = false;
            while (fast!=null&&fast.next!=null)
            {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast)
                    isCircle = true;
            }
            if (isCircle == false)
            {
                return null;
            }
            ListNode start = head;
            while (slow != start)
            {
                slow = slow.next;
                start = start.next;
            }
            return start;
        }
    }