[LeetCode]Linked List Cycle

hashmap的方法显而易见，存所有经过的节点再看以前是不是访问过即可。O(1)空间的做法需要双指针，快指针每次移动2个节点，慢指针每次移动1个节点，如果有cycle的话，两个指针最后是会相遇的。假设换的入口节点为0，最后一个节点为k - 1，长度为k。当慢指针进入环的时候:

• 如果快指针在0，那么我们找到环
• 如果快指针在x，0 < x < k，快指针和慢指针的距离小于k。由于快指针每次比慢指针多移动1的距离，所以在慢指针转完k距离回到0节点之前，快指针就可以赶上慢指针。

所以如果存在环的话，快指针一定会和慢指针相遇，假设环的长度为K，非环部分长度为L，时间复杂度O(L + K)，常数空间。代码如下:

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool hasCycle(ListNode *head) {
	auto slow = head, fast = head;
	while(fast && fast->next)
	{
	fast = fast->next->next;
	slow = slow->next;
	if(fast == slow)return true;
	}
	return false;
	}
	};

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