tag：双指针——快慢指针
难度：medium
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2： 输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3： 输入：head = [1], pos = -1 输出：no cycle 解释：链表中没有环。
进阶： 你是否可以不用额外空间解决此题？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Note：对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针，分别命名为slow 和fast，起始位置在链表的开头。每次fast 前进两步，slow 前进一步。如果fast可以走到尽头，那么说明没有环路；如果fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻slow 和fast 相遇。当slow 和fast 第一次相遇时，我们将fast 重新移动到链表开头，并让slow 和fast 每次都前进一步。当slow 和fast 第二次相遇时，相遇的节点即为环路的开始点。
/** * 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) { ListNode *fast = head; ListNode *slow = head; while(true){ while(fast!=nullptr && fast->next!=nullptr){ //while(fast!=nullptr){ // if(fast==nullptr){ // return nullptr; // } //if(fast->next->next!=slow->next){ // if(fast!=slow){ // fast = fast->next->next; // slow = slow->next; // }else{ // //if(fast->next->next==slow->next){ // fast = head; // //while(fast->next!=slow->next){ // while(fast!=slow){ // fast = fast->next; // slow = slow->next; // } // return fast; // } fast = fast->next->next;//提前搞一次，避免在开始就返回head slow = slow->next; if(fast==slow){ fast = head; while(fast!=slow){ fast = fast->next; slow = slow->next; } return fast; } } return nullptr;//nullptr == NULL } }; //另解 ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; // 判断是否存在环路 do { if (!fast || !fast->next) return nullptr; fast = fast->next->next; slow = slow->next; } while (fast != slow); // 如果存在，查找环路节点 fast = head; while (fast != slow){ slow = slow->next; fast = fast->next; } return fast; }