[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 <iostream>
    #include <vector>
    #include <algorithm>
    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;
        }
    };