题目：

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

~~~python # 样例1 输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点

样例2

输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点


<!--more-->

### 解题方法：

{% note warning%}

哈希表法思路比较简洁明了，需要注意的是存储的是node地址，而非值；快慢指针是很重要的技巧，需要熟练掌握，优点是时间复杂度和哈希表法相同，但是只用$O(1)$的额外空间

{% endnote %} 

1. **哈希表法：**遍历链表，每经过一个node就把他的地址放到表里，第一个重复的地址即为圈的首节点

   {% note primary %}

   时间复杂度为$O(n)$，额外的空间复杂度为$O(n)$

   {% endnote %} 

3. **快慢指针：**

   {% note primary %}

   时间复杂度为$O(n)$，额外的空间复杂度为$O(1)$

   {% endnote %} 


### 解法一：哈希表法

{% note warning %}

- map、set、unordered_map、unordered_set总结：https://blog.csdn.net/qq_30815237/article/details/91047041


{% endnote %}

~~~c++
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while(head != NULL)
        {
            if(visited.count(head) == 1) 
            // if(visited.find(head) != visited.end())
            // count实测比find函数快，执行时间分别是4ms和8ms
            {
                return head;
            }
            else
            {
                visited.insert(head);
                head = head->next;
            }
        }
        return NULL;
    }
};

解法二：快慢指针

解题思路：

使用两个指针，fast与slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇
- 此时fast走的距离为 \(a+n(b+c)+b\)，此时slow走了 \(a+m(b+c)+b\) 的距离
- 根据定义，fast走了slow的两倍距离，因此 \(a+n(b+c)+b=2(a+m(b+c)+b)\)
- 解得 \(a=(n-2m-1)*(b+c)+c\)
相遇后：新建指针p = head从头走，slow和p一起走，当p走了\(a\)步时，slow也走了\((n-2m-1)*(b+c)+c\) 步，即\(n-1\)圈再加上额外的\(c\)步，即相遇时为环的起点

证明1：快慢指针一定会相遇吗？（数学归纳法）

如果两指针间距为一，则两者再走一次就相遇了
如果间距为n，则两者再走一次后，间距就变为 \(n+1-2=n-1\) 了，重复这个过程，直至两者相遇

证明2：快指针的速度是慢指针的n倍时，两者是否还会相遇？

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL) return NULL;
        ListNode *slow = head, *fast = head, *p = head;
        while(fast->next!=NULL)
        {
            if(fast->next->next == NULL) break;
            fast = fast->next->next;
            slow = slow->next;            

            if(fast == slow)
            {
                // cout << fast->val;
                while(slow != p) 
                // p和slow刚好在环的起始节点相遇，两者走的距离都是a=(n-1)*(b+c)+c
                {
                    slow = slow->next;
                    p = p->next;
                }
                return p;
            }
            
        }
        return NULL;
    }
};