[LeetCode]Linked List Cycle II

和Linked List Cycle是类似的，hashmap的解法很容易想 。O(1) space的方法，也需要用双指针。具体的算法如下：

1. 一快一慢双指针，快指针每次移动2的距离，慢指针移动1，存在环的话最终会相遇，这一点在前一道题中已经证明过。假设相遇的点为x
2. 快指针重新移到head，慢指针仍然指向x，快慢指针此时每次只移动1的距离，两个指针一定相交于换的入口处

为了证明第二点，我们需要定义几个参数。假设环的入口节点为0，长度为K，最后一个节点为K - 1。假设从head到0节点的长度为L。在前一道题中我们已经证明过，不管环有多大，慢指针在跑完一圈之前就会被快指针赶上，假设慢指针跑过的路程为m，快慢指针第一次相遇的节点距离0节点为x，在相遇之前，快指针可能已经跑了n圈，下列方程一定成立：

• 2 * m =  2 * (L + x) = L + x + n * K

右边是快指针跑过的距离，左边是慢指针跑过的距离乘以2，两者肯定相等。进一步我们可以得到：

• L = n * K - x

两边对K取余，我们有:

• L % K = (K - x) % K

上面这条等式代表的正是x和圆环的入口0节点的距离对K取余后就等于节点0和head的距离L对K取余。也就是说，不管L有多大，K有多小，慢指针从x开始继续移动不管转了多少圈，最后一定会和快指针在0节点相遇。第二点得证。时间复杂度O(N)，常数空间，代码如下:

	/**
	* 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) {
	auto fast = head, slow = head;
	while(fast && fast->next)
	{
	fast = fast->next->next;
	slow = slow->next;
	if(slow == fast)break;
	}
	if(!fast || !fast->next)return nullptr;
	fast = head;
	while(slow != fast)
	{
	fast = fast->next;
	slow = slow->next;
	}
	return slow;
	}
	};

view raw Linked List Cycle II.cpp hosted with ❤ by GitHub