EEPW论坛

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

Follow up:

Can you solve it without using extra space?

题意：找到循环链表的初始位置。

思路：

1.还是先用快慢指针方法，找出快慢指针相遇的点；

2.重新定义两个指针，一个为head，另一个为相遇的节点；

3.然后两个指针每次走一步，相遇点则是链表环的起点；

1. class Solution  

2. {  

3. public:  

4.     ListNode* detectCycle(ListNode* head)  

5.     {  

6.         if (head==NULL)  

7.         {  

8.             return NULL;  

9.         }  

10.   

11.         ListNode* slow = head;  

12.         ListNode* fast = head;  

13.   

14.         while (fast!=NULL && fast->next!=NULL)  

15.         {  

16.             slow = slow->next;  

17.             fast = fast->next->next;  

18.   

19.             if (slow == fast)  

20.             {  

21.                 ListNode* node1 = head;  

22.                 ListNode* node2 = fast;  

23.                 while (node1!=node2)  

24.                 {  

25.                     node1 = node1->next;  

26.                     node2 = node2->next;  

27.                 }  

28.   

29.                 return node1;  

30.             }  

31.         }  

32.   

33.         return NULL;  

34.     }  

35. };