题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

示例：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解答

/**
 * 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) {
        //首先判断链表是否有环：定义fast和slow两个指针，fast一次走2步，slow一次走1步
        //当fast与slow相遇时，则代表有环
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast != NULL && fast->next != NULL)
        {
            fast  = fast->next->next;
            slow = slow->next;

            //fast与slow相遇，有环
            if(fast == slow)
            {
                //定义a,b两个指针，a指向链表头结点，b指向fast与slow相遇的结点
                //a,b分别每次走一步，相遇时，就是入环所在位置
                ListNode *a = head;
                ListNode *b = fast;

                while(a != b)
                {
                    a = a->next;
                    b = b->next;
                }
                //有环，返还入口结点
                return a;
            }

        }
        // 无环
        return NULL;
    }
};