多种方法求环入口节点，总有一种适合你

链表中环的入口结点

http://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4

下酒菜：带环单链表如果求是否有环？

快指针一下走两步，慢指针一下走一步，最终它们会在环中相遇

简单的有限证明：
        首先，它们都会进入环
        假设快指针在慢指针后面一步，下一次就追上了。（可在脑海中想一想）
        后面两步，由于快指针比慢指针多走一步，一次后就在后面一步，下一次就追上了。
        后面n步，n - 1次后就在后面一步，下一次就追上了。

方法一：断链法求环入口

现在已经已经会求单链表有无环了，下面由另一个常见的问题，引出此方法：

问题：如何判断两个无环链表是否相交，如果相交，求出第一个相交的节点

1 长链表指针先走long_len -short_len的距离，然后一一进行比较

2 将一个链表尾部与头部相连，形成环；
一个快指针，一个慢指针，最终它们相遇则相交，未成环的指针点走到了nullptr，则不相交；

下面问题来了：

                    上面把链表相交问题转化成了环问题。
                    那么从环问题的角度来看，如果把环断开，就转变变成了相交问题。
                    那么求环的入口问题，可以转化为求两个单链表求交点的问题

图形展示：

        如图：断开后（fast = fast->next; slow->next = NULL;）
        弄直了来看，就是一个活生生的链表相交问题，环入口点即是链表相交点。

        极限情况：

            1，fast slow都在环入口上，断开后，新链和原链，相交于最后一个节点，能测出来
            2，fast slow都在环入口的前一个节点，断开后，新链表第一个节点就在原链表上。能测出来

C++代码：

class Solution {
public:
	ListNode* EntryNodeOfLoop(ListNode* pHead)
	{
		ListNode* fast = pHead, *slow = pHead;
		while (fast) {
			if (!fast->next)  //奇数个节点，且到了末尾
				return NULL;
			fast = fast->next->next;
			slow = slow->next;
			if (fast == slow) {  //相遇，有环
				fast = fast->next;
				slow->next = NULL;  //解链，fast是第二个链表的头节点，slow是两个链表的尾节点
				int l1 = ListLength(fast);
				int l2 = ListLength(pHead);
				if (l1 < l2) {  //fast更长
					swap(l1, l2);
					swap(pHead, fast);
				}
				for (int i = 0; i < l1 - l2; i++)  //长链表先走l1-l2长度
					fast = fast->next;
				while (fast) {  //再一起走
					if (fast == pHead)
						return fast;
					fast = fast->next;
					pHead = pHead->next;
				}
			}
		}
		return NULL;  //偶数个节点，退出上面循环
	}

	int ListLength(ListNode* head) {  //求链表长度
		int length = 0;
		while (head) {
			length++;
			head = head->next;
		}
		return length;
	}

};

方法二：数学方法求环入口

先看一张图片，等会会用上：

        如果fast和slow相遇时，slow已经走完一圈，fast早就把slow追上了
        所以当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步，则fast走了2s步，又由于
        fast走过的步数 = s + n*r（快指针比慢指针走的s多走n圈，r为圈大小），则有下面的等式：
        2*s = s + n * r ; (1)
         => s = n*r (2)
        如果假设整个链表的长度是L，入口和相遇点的距离是x（如上图所示），起点到入口点的距离是a(如上图所示)，则有：
        a + x = s = n * r; (3) 由（2）推出
        a + x = (n - 1) * r + r = (n - 1) * r + (L - a) (4) 由环的长度 = 链表总长度 - 起点到入口点的距离求出
        最终结果：
        a = (n - 1) * r + (L -a -x) (5)

        即：起点到入口的距离 = 从相遇点到环入口的距离 + （n-1）*r
        简单的说：让一根指针从开始走，一根指针从相遇点走，最终它们会在环入口点相遇，至于第二根指针在环中走的圈数，我们并不关心。

C++代码：

class Solution {
public:
	ListNode* EntryNodeOfLoop(ListNode* pHead)
	{
		ListNode* fast = pHead, *slow = pHead;
		while (fast) {
			if (!fast->next)  //奇数个节点，且到了末尾
				return NULL;
			fast = fast->next->next;
			slow = slow->next;
			if (fast == slow) {   //相遇，有环
				while (1) {  //一个从相遇点走，一个从开头走，必会相遇，相遇点则是入口点
					if (fast == pHead)
						return fast;
					fast = fast->next;
					pHead = pHead->next;
				}
			}
		}
		return NULL;  //偶数个节点，退出上面循环
	}
};

怎么样，是不是简单多了

不得不感叹，不怕牛的程序员，就怕数学好的程序员！