[LeetCode]Linked List Cycle II

原题链接：http://oj.leetcode.com/problems/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?

题解：

　　这道题的v1版本是判断一个单链表是否有环，当时我们采用的是快慢指针的方法。传送门：http://www.cnblogs.com/codershell/p/3600100.html

　　然而本题有所加强，需要找出环的起点。对于一个存在环的单链表，我们有如下示意图：

　　如图所示，慢指针在相遇时走过的距离为S1 = A+B；快指针走过的距离为：S2 = A+B+n*周长。

　　又由于快指针的速度是慢指针的2倍，因此有S2 = 2*S1.整理有

　　A = n*周长 - B

　　此时，如果将一个指针移到起点，另一个指针依然在相遇点，保持同意速度，相遇点即为环的起点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL)return NULL;
        ListNode*p = head,*q = head;
        while(p!=NULL && q!=NULL){
            p = p->next;
            q = q->next;
            if(q!=NULL)
                q = q->next;
            if(p==q)
                break;
            
        }
        if(q == NULL)
            return NULL;
            
        p = head;  
        while (p != q){  
            p = p->next;  
            q = q->next;  
        }  
        return q;  
    }
};