141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

S1：hashtable 存储出现过的指针

S2：fast slow poniter 出现环必相遇

    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast) return true;
        }
        return false;
    }

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.

S1：hashmap,遇到出现过的节点pointer就返回

S2: slow fast pointer + math

1. slow, fast pointer 前行（slow走1步fast走2步）直到相遇，不相遇则返回NULL

2. 将slow(or fast)pointer放回head，两者前进（都走1步）直到相遇，相遇点即环起点

    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return NULL;
        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) break;
        }
        if(fast != slow) return NULL;
        fast = head;
        while(fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }