面试题 02.08. 环路检测

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11      ListNode *detectCycle(ListNode *head) 
12      {
13         
14         ListNode* slow = head;
15         ListNode* fast = head;
16 
17         while(fast && fast->next)
18         {
19             slow = slow->next;
20             fast = fast->next->next;
21 
22             if(slow == fast)  // 相遇
23             {
24 
25                 break;
26             }
27         }
28 　　　　　// 若无相会处，则无环路。
29         if(fast == nullptr || fast->next == nullptr)
30         {
31             return nullptr;
32         }
33 
34         ListNode* p1 = head;
35         ListNode* p2 = fast;
36         // 若两者以相同的速度移动，则必然在环路起始处相遇
37         while(p1 != p2)
38         {
39             p1 = p1->next;
40             p2 = p2->next;
41         }
42 
43         return p1;
44     }
45 };