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.jiuzhang.com/ *//** * 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;    }}