142. 环形链表 II

 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 {
11 public:
12     ListNode *detectCycle(ListNode *head) 
13     {
14         //链表的长度小于等于1
15         if(head == NULL || head->next == NULL) return NULL;
16         ListNode *fast = head,*slow = head;
17         while(fast && fast->next && slow)
18         {
19             //快指针走两步，慢指针走一步，如果相等，结束循环。
20             fast = fast->next->next,slow = slow->next;
21             if(fast == slow) break;
22         }
23         //如果没有环，则至少有一个走到NULL
24         if(fast == NULL || slow == NULL) return NULL;
25         fast = head;//快指针重新回到起点
26         while(fast && slow)//快慢指针同时走
27         {
28             if(fast == slow) return fast;//首先判断是否相遇
29             fast = fast->next,slow = slow->next;
30         }
31         return NULL;
32     }
33 };