LeetCode 142. Linked List Cycle II

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

思路

其实还有更简单的方法，在《Cracking the Coding Interview》上有提到。通过数学计算可以推导出来，用快行指针的方法判断出环后，可以不用计算环大小，把快指针变慢然后放到链头上，两个指针继续走到相碰就剩入口了。
分为三步：判断环，计算环的大小，找到入口
判断环就是老一套，用2倍速指针就行，这个之前的题目里头有；
计算环的大小k，环的大小么，刚才相碰的地方找个指针绕圈圈走。记个数，再碰到相遇地点就是环大小了；
找到入口后，我们有两个普通速度的指针pA,pB，让其中一个pA先往前走k步，然后两个一起开始挪动，可以知道，如果pA与pB又相遇了，那相遇点就是环的入口了。此时pA比pB刚好多走了一整圈。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* meetingNode(ListNode* head){
        //Find the meeting node
        if(head == NULL)
            return NULL;
        ListNode* slow = head->next;
        if(slow == NULL)
            return NULL;
        ListNode* fast = slow->next;
        while(fast != NULL && slow != NULL){
            if (slow == fast)
                return slow;
            slow = slow->next;
            fast = fast->next;
            if(fast != NULL)
                fast = fast->next;
        }
        return NULL;
    }
    ListNode *detectCycle(ListNode *head) {
        ListNode* meet = meetingNode(head);
        if(meet == NULL)
            return NULL;
        //Get loop size
        ListNode* temp = meet->next;
        int count = 1;
        while(temp != meet){
            count++;
            temp = temp->next;
        }
        //Pick one pointer at start, move `count` steps forward
        temp = head;
        meet = head;
        while(count > 0){
            count--;
            meet = meet->next;
        }
        //Find the cycle start
        while(temp != meet){
            temp = temp->next;
            meet = meet->next;
        }
        return meet;
    }
};