142. 环形链表 II

原题链接：142. 环形链表 II

solution:        用哈希表存储

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set map;
        ListNode *cur = head;
        while(cur != nullptr){
            map.insert(cur);
            cur = cur->next;
            if(map.count(cur)){ //如果已经存在,则break;
                break;
            }
        }
        return cur;  
    }
};

双指针：如果没有环，返回nullptr;

如果有环,快慢指针一定会相遇,假设快指针一次走2步,满指针一次走1步,相遇的时候慢指针走了s步,快指针走了f = 2s步,并且f = s + nb，其中n是圈数,b是环的长度。可以解出来,s = nb; 假设head到第一个入环点的距离为a，则慢指针再走a步就到了入环点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return nullptr;
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast->next != nullptr && fast->next->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;  //快指针每次走2步
            if(fast == slow){
                ListNode *cur = head;
                while(cur != slow){
                    cur = cur->next;
                    slow = slow->next;
                }
                return cur;
            }

        }
        //跳出while循环肯定没有环
        return nullptr;
    }
};