LeetCode:环形链表入口_循环链表找入口

寻找环形链表入口有两种解决方案，一种是哈希法，遍历链表时，检查哈希表，如果发现存在，则说明这个节点已经被走过，即是环形入口，代码如下

ListNode *detectCycle(ListNode *head) 
{
     unordered_set<ListNode*> temp;
     ListNode* flag = head;
     while(flag != nullptr)
     {
        if(temp.find(flag) != temp.end())
            return flag;
        temp.emplace(flag);
        flag = flag->next;
     }
     return nullptr;
}

这种方案是最容易想到的，理解起来很很简单，但效率却不够高，尤其在链表数量很多的时候，会开辟大量的内存空间用来存放节点，虽说是用了哈希表，但总体查找也比较费时。

第二种方案比较生僻，我个人称为路径法，这个一般不容易想到，我学习了这个方案后自己再小结一下，争取让看本文的同学能够更清楚地get到原理。

假设环形链表如下，起点为A，入口为B。

现添加一个快指针fast，一个慢指针slow，从头开始跑，fast每步进2，slow每步进1。当fast进入环形的时候，slow肯定还没到，因为slow走得慢嘛！于是fast就在环里转啊转，转啊转，转到某个点和slow相遇了，设相遇点为C。

这里有个问题需要解释一下，为什么快慢指针在环形内一定相遇？因为fast每步+2，slow每步+1，意味着相对来说fast每次比slow多走1步。则当slow来到B点的时候，fast在环里某个位置，二者就同时在环里赛跑了，好家伙，我fast每次都比你slow多1步，一个环内，我不肯定能追上你？

设相遇时slow走了距离x，环的周长为y，快指针走了n圈。二者既然在C点相遇了，则这C点肯定是之前fast走过的，则可以想象为第一次fast走到C的时候，slow还在慢慢悠悠的晃来，于是fast就在原地转圈，1圈，2圈，....n圈之后终于等到了slow！此时slow走了x，fast走了x+ny(首次走到B点行进了x，又转了n圈)。只要二者还在走，则fast走的步数永远是slow的两倍，所以有

fast的步数=x+ny = x*2，消去x，得到x=ny。这说明什么？说明假如有一个普通指针i从A出发，一个普通指针j从C触发绕圈，则当i走到C的时候，j恰好绕了n圈！二者在C点相遇。

我这里为什么强调i j 是普通指针呢？普通指针意味着它们每次的步数都是1，那么当它们在C点相遇的时候，因为步数都是1，所以从B到C它们都一直是重合的，也就是说，B是它们开始重合的起始节点！

那么当快慢指针相遇的时候，我们只要从A发射i，从C发射j，i++,j++,当二者重合的时候，不就是环的入口了吗？！原理get！于是有如下代码

ListNode* detectCycle(ListNode* head)
	{
		if (head == nullptr)
			return nullptr;
		ListNode* fast = head;
		ListNode* slow = head;
		while (fast != nullptr && fast->next != nullptr)
		{
			fast = fast->next->next;
			slow = slow->next;
			if (fast == slow)
			{//快慢相遇，发射i j 
				ListNode* i = head;
				ListNode* j = fast;
				while (i != j)
				{
					i = i->next;
					j = j->next;
				}
				return i;
			}
		}
		return nullptr;
	}

至此，环形入口成功被我们找到了。