Linked List Cycle II
题目:
Given a linked list, return the node where the cycle begins.
If there is no cycle, return null.
分析:
这道题目印象是比较深的,主要需要注意slow和fast都从head开始,不引入dummy。只有这样,计算才是对的,entry才能遇见slow。
这和cycle I并不一样,因为在cycle I里面,你slow和fast不同时出发并没有问题,迟早都会遇见,但是在II里面必须同时出发,数学计算才是对的。
解法:
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
ListNode *detectCycle(ListNode *head) {
// write your code here
if (head == NULL) {
return NULL;
}
ListNode* slow = head;
ListNode* fast = head;
bool isCycle = false;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// found cycle!
isCycle = true;
break;
}
}
if (!isCycle) {
return NULL;
}
ListNode* entry = head;
while (entry != slow) {
entry = entry->next;
slow = slow->next;
}
return entry;
}
};