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?
思路
这题是Linked List Cycle的进阶版
Given a linked list, determine if it has a cycle in it.
bool hasCycle(ListNode *head) {
if(head == NULL) return false; //带环链表还要考虑只有单个元素的情况
ListNode *faster = head, *slower = head;
while(faster->next != NULL && faster->next->next != NULL && slower->next != NULL){//直接判断faster->next->next != NULL会抛错
faster = faster->next->next;
slower = slower->next;
if(faster == slower)
return true;
}
return false;
}
faster和slower相遇之后必然在环上，让slower再走一圈计算环的长度len。另让两个指针p1,p2从head开始走，p1比p2先走len步，这样当p2走到环开始处时，正好p1与p2第一次相遇。
ListNode *detectCycle(ListNode *head) {
if(head == NULL) return NULL;
//带环链表要考虑只有单个元素的情况
ListNode *faster = head, *slower = head;
while(faster->next != NULL && faster->next->next != NULL && slower->next != NULL){//直接判断faster->next->next != NULL会抛错
faster = faster->next->next;
slower = slower->next;
if(faster == slower){
ListNode *p1 = head;//另让两个指针p1,p2从head开始走
ListNode *p2 = head;
slower = slower->next;//让slower再走一圈计算环的长度len
p1 = p1->next;//设len是环的长度，p1比p2先走len步
if(faster == slower) return faster;//自环
while(faster != slower){
slower = slower->next;
p1 = p1->next;
}
while(p1 != p2){//当p1与p2第一次相遇时，正好p2走到环开始处
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
}
return NULL;
}