142. Linked List Cycle II

   
          p1为环开始的节点，p2为fast指针和slow指针相遇的节点。A 、B、 C分别为三段的距离。当相遇的时候slow指针经过的路程为（A + B）而fast指针经过的路程为(A + B + C + B)。同时fast经过的路程又是slow的两倍，所以又（A + B + C + B）= 2（A + B）所以最后得到A = C！那么当两者相遇的时候，只需要将slow指针放回到起始节点，而fast指针继续在原有位置上向前走。两个指针一相同的速度访问节点。当两者再次相遇的时候，相遇的节点就是环路起始节点p1。实现代码如下：

/**
 * 本代码由九章算法编辑提供。没有版权欢迎转发。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，九章强化班，Java入门与基础算法班，
 * - 更多详情请见官方网站：http://www./
 */

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next==null) {
            return null;
        }

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