Linked List Cycle II(Medium)

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

Just make a easier understanding. Suppose the first meet at step k,the distance between the start node of list and the start node of cycle is s, and the distance between the start node of cycle and the first meeting node is m. Then 2k = (s + m + n1r) = 2(s + m + n2r) ==> s + m = nr. Steps moving from start node to the start of the cycle is just s, moving from m by s steps would be the start of the cycle, covering n cycles. In other words, they meet at the entry of cycle.

public ListNode detectCycle(ListNode head) {
        if(head==null || head.next==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;
        }
        //如果while是因为遇到链表尾即没有环 则返回null；
        if(fast==null || fast.next ==null) 
            return null;

        //如果有环则从head再次出发一个节点（速度和slow一样），
        //这个节点和slow相遇的节点即为环的开始点
        else{
            ListNode trird = head;
            while(trird!=slow){
                trird = trird.next;
                slow = slow.next;
            }
            return trird;
        }
    }