【题解】【链表】【Leetcode】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?

思路

这题是Linked List Cycle的进阶版

Given a linked list, determine if it has a cycle in it.

 1 bool hasCycle(ListNode *head) {
 2     if(head == NULL) return false; //带环链表还要考虑只有单个元素的情况
 3     ListNode *faster = head, *slower = head;
 4     while(faster->next != NULL && faster->next->next != NULL && slower->next != NULL){//直接判断faster->next->next != NULL会抛错
 5         faster = faster->next->next;
 6         slower = slower->next;
 7         if(faster == slower) 
 8             return true;
 9     }
10     return false;
11 }

faster和slower相遇之后必然在环上，让slower再走一圈计算环的长度len。另让两个指针p1,p2从head开始走，p1比p2先走len步，这样当p2走到环开始处时，正好p1与p2第一次相遇。

 1 ListNode *detectCycle(ListNode *head) {
 2     if(head == NULL) return NULL;
 3     //带环链表要考虑只有单个元素的情况
 4     ListNode *faster = head, *slower = head;
 5     while(faster->next != NULL && faster->next->next != NULL && slower->next != NULL){//直接判断faster->next->next != NULL会抛错
 6         faster = faster->next->next;
 7         slower = slower->next;
 8         if(faster == slower){
 9             ListNode *p1 = head;//另让两个指针p1,p2从head开始走
10             ListNode *p2 = head;
11             slower = slower->next;//让slower再走一圈计算环的长度len
12             p1 = p1->next;//设len是环的长度，p1比p2先走len步
13             if(faster == slower) return faster;//自环
14             while(faster != slower){
15                 slower = slower->next;
16                 p1 = p1->next;
17             }
18             while(p1 != p2){//当p1与p2第一次相遇时，正好p2走到环开始处
19                 p1 = p1->next;
20                 p2 = p2->next;
21             }
22             return p2;
23         }
24     }
25     return NULL;
26 }