一、环形链表 II
进阶：用O(1)实现。
二、思路
快慢指针，其实和【环形链表 I】差不多，那个是判断是否有环，现在这题是找出开始入环的第一个结点。同样适用快慢指针，由下图分析，因为快指针的速度设置为慢指针的2倍（每次满指针走1步，快指针走2步），由2(F+a)= F+a+b+a，得到F=b的关键信息。所以当两个指针第一次相遇后，我们让快指针回到head原点，这时候让快指针和满指针以相同速度前进，即快指针走F步，慢指针走b步，就能够到达所求的环入口，进行相遇了。
三、代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { if(head == NULL || head->next == NULL){ return NULL; } ListNode* slow = head; ListNode* fast = head; bool flag = false; while(fast != NULL && fast->next != NULL){ slow = slow->next; fast = fast->next->next; if(fast == slow){ flag = true; break; } } ListNode* fast2 = head; while(fast2 != slow && flag == true){ fast2 = fast2->next; slow = slow->next; } if (flag == false){ return NULL; }else{ return fast2; } } };
