LeetCode OJ-- Linked List Cycle II **

https://oj.leetcode.com/problems/linked-list-cycle-ii/

判断一个链表中是否有环，如果有，求环的开始位置。

按照上道题目的想法，先判断出是否有环来，同时能得出 slow走了多少步设为 paces。也就是说再次相遇的时候，fast比slow多走了环的n倍的大小。

然后slow = head, fast = head,然后让fast = fast->next往后走 paces 步，之后slow 和 fast再一起走，等到相遇的时候，就是那个环开始地方。

#include <iostream>

#include <vector>

#include <string>

#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 == NULL)

            return false;

        ListNode *slow = head;

        ListNode *fast = head;

        int space = ;

        while(fast)

        {

            if(fast->next)

                fast = fast->next->next;

            else

                return NULL;

            slow = slow->next;

            space++;

            if(fast == slow)

                break;

        }

        if(fast == NULL)

            return NULL;

        slow = head;

        fast = head;

        while(space--)

        {

            fast = fast->next;

        }

        while(fast!=slow)

        {

            fast = fast->next;

            slow = slow->next;

        }

        return slow;

    }

};

int main()

{

    class Solution mys;

    ListNode *n1 = new ListNode();

    ListNode *n2 = new ListNode();

    /*ListNode *n3 = new ListNode(3);

    ListNode *n4 = new ListNode(4);*/

    n1->next = n2;

    /*n2->next = n3;

    n3->next = n4;

    n4->next = n3;*/

    mys.detectCycle(n1);

}