Leetcode 141/142: cycle in Linklist

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?

 

判断一个linklist有没有cycle, 两个指针slow, fast同向而行，如果fast 和slow最后能够相交，说明linklist有环。 

怎么判断cycle的点呢？ slow停在原处，fast从头开始走，fast此时每次只走一步，最后slow 和fast相交的时候就是 cycle的点。 

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //sanity check
        if (head == NULL || head->next == NULL) return NULL;
        //check if there is a cycle
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        if (fast == NULL || fast->next == NULL) return NULL;
        fast = head;
        while (slow != fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};