Leetcode 鏈表 Linked List Cycle II

Leetcode 鏈表 Linked List Cycle II

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

題意：給定一個單鏈表，判斷該鏈表中是否存在環，如果存在，返回環開始的節點
思路：
1.定義兩個指針，快指針fast每次走兩步，慢指針s每次走一次，如果它們在非尾結點處相遇，則說明存在環
2.若存在環，設環的周長為r，相遇時，慢指針走了 slow步，快指針走了 2s步，快指針在環內已經走了 n環，
則有等式 2s = s + nr 既而有 s = nr
3.在相遇的時候，另設一個每次走一步的慢指針slow2從鏈表開頭往前走。因為 s = nr，所以兩個慢指針會在環的開始點相遇
復雜度：時間O(n)

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};


ListNode *detectCycle(ListNode *head) {
	if(!head || !head->next) return NULL;
	ListNode *fast, *slow, *slow2;
	fast = slow = slow2 = head;
	while(fast && fast->next){
		fast = fast->next->next;
		slow = slow->next;
		if(fast == slow && fast != NULL){
			while(slow->next){
				if(slow == slow2){
					return slow;
				}
				slow = slow->next;
				slow2 = slow2->next;
			}
		}
	}
	return NULL;
}