Linked List Cycle II

题目：

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

分析：

这道题目印象是比较深的，主要需要注意slow和fast都从head开始，不引入dummy。只有这样，计算才是对的，entry才能遇见slow。

这和cycle I并不一样，因为在cycle I里面，你slow和fast不同时出发并没有问题，迟早都会遇见，但是在II里面必须同时出发，数学计算才是对的。

解法：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The node where the cycle begins. 
     *           if there is no cycle, return null
     */
    ListNode *detectCycle(ListNode *head) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        bool isCycle = false;

        while (fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                // found cycle!
                isCycle = true;
                break;
            }
        }

        if (!isCycle) {
            return NULL;
        }

        ListNode* entry = head;

        while (entry != slow) {
            entry = entry->next;
            slow = slow->next;
        }

        return entry;
    }
};