[LeedCode OJ]#142 Linked List Cycle II

[LeedCode OJ]#142 Linked List Cycle II

題意：

對於一個鏈表，判斷其是否有環，有環則返回環的起始位置。

思路：

通過141題，我們知道可以通過快慢指針來判斷是否有環，現在我們假設兩個指針相遇在z點，如圖

那麼我們可以知道fast指針走過a+b+c+b

slow指針走過a+b

那麼2*(a+b) = a+b+c+b

所以a = c

那麼此時讓slow回到起點，fast依然停在z，兩個同時開始走，一次走一步

那麼它們最終會相遇在y點，正是環的起始點

/**
 * 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)
		{
			ListNode *slow = head;
			ListNode *fast = head;
			do
			{
				if(!slow||!fast)
					return nullptr;
				slow = slow->next;
				fast = fast->next;
				if(fast)
					fast = fast->next;
				else
					return nullptr;
			}
			while(slow!=fast);

			slow = head;
			while(slow!=fast)
			{
				slow = slow->next;
				fast = fast->next;
			}
			return slow;
		}
};