[LeetCode]142.Linked List Cycle II

题目：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?

分析：

首先使用快慢指针技巧，如果fast指针和slow指针相遇，则说明链表存在环路。当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈了（1<=n）设slow走了s步，则fast走了2s步（fast步数还等于s加上环在多转的n圈），设环长为r则：

                    2s = s + nr
                    s = nr

设整个链长L，环入口点与相遇点距离为a，起点到环入口点距离为x，则：

             x + a = s = nr = (n - 1)r + r = (n - 1)r + L - x
             x = (n - 1)r + L - x - a

L -x -a 为相遇点到环入口点的距离，由此可知，从链表开头到环入口点等于n - 1圈内环 + 相遇点到环入口点，于是我们可以从head开始另设一个指针slow2，两个慢指针每次前进一步，他们两个一定会在环入口点相遇。

代码：

    /**------------------------------------
    *   日期：2015-02-05
    *   作者：SJF0115
    *   题目: 142.Linked List Cycle II
    *   网址：https://oj.leetcode.com/problems/linked-list-cycle-ii/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include 
   
     #include 
    
      #include 
     
       using namespace std; struct ListNode{ int val; ListNode *next; ListNode(int x):val(x),next(NULL){} }; class Solution { public: ListNode *detectCycle(ListNode *head) { if(head == nullptr){ return nullptr; }//if ListNode *slow = head,*fast = head,*slow2 = head; while(fast != nullptr && fast->next != nullptr){ slow = slow->next; fast = fast->next->next; // 相遇点 if(slow == fast){ while(slow != slow2){ slow = slow->next; slow2 = slow2->next; }//while return slow; }//if }//while return nullptr; } };