[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;
        }
    };