Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

http://www.lintcode.com/en/problem/linked-list-cycle-ii/

Discussion

只有cycle开始的node是有两个前置节点的，所以用hash记录当前结点和它的前置节点，如果前置节点对不上了，说明找到了。

用快慢指针也可以解决，而且是O(1)的space，容我再看吧。。

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
        unordered_map<ListNode*, ListNode*> nodeCnt;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *cur = head;
        ListNode *pre = dummy;
        while(cur) {
            if(nodeCnt.find(cur) == nodeCnt.end()) {
                nodeCnt[cur] = pre;
            } else if(nodeCnt[cur] != pre) {
                return cur;
            }
            pre = cur;
            cur = cur->next;
        }
        return NULL;
    }
};

快慢指针的方法：

ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;

        while (fast && fast->next) {
            slow = slow->next, fast = fast->next->next;
            if (slow == fast) {  // There is a cycle.
                slow = head;
                // Both pointers advance at the same time.
                while (slow != fast) {
                    slow = slow->next, fast = fast->next;
                }
                return slow;  // slow is the begin of cycle.
        }
        return nullptr;  // No cycle.
    }