这个题看似简单，其实想讲清楚原理并不简单：

1. 首先要确定链表中是否包含了环；
2. 用双指针判断环中节点数（其实不是求具体的节点数，只是得出环中节点数的整数倍），慢指针每次走一步，快指针每次走两步，如果链表中有环，它们肯定会相遇，假设相遇时慢指针走了k步，那么快指针肯定走了2k步，快指针比慢指针多走了k步，而且快指针比慢指针在环中多转了若干圈（具体多少圈我们不知道，因为不知道这个环有多长，其实也不需要知道），也就是说：多走的这k步肯定是环中节点数目的整数倍（因为多走了k步，对应多转了若干圈）；
3. 此时让快指针继续指向它们相遇的节点，慢指针则重新指向链表头结点，两指针再次齐步走，当慢指针走到环入口时，因为快指针比它多走了k步，k是环内节点个数的整数倍，表示快指针刚好在环入口转了若干圈后回到了环入口节点！此时两指针正好相遇。

2022-03-01，百度自动驾驶技术部-高精地图web后端，经理面的时候被问到这个原理，结果我忘记了，没答上来哈哈。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == nullptr) return nullptr;

        ListNode *fast = head, *slow = head;

        while (fast)
        {
            fast = fast->next;               //快指针每次走两步，慢指针每次走一步
            slow = slow->next;

            if (fast) fast = fast->next;
            else return nullptr;

            if (fast == slow)               //第一次相遇时，即得到了环中节点的整数倍
            {
                slow = head;                //慢指针重新指向链表头节点
                while (fast != slow) 
                {
                    fast = fast->next;
                    slow = slow->next;
                }

                return slow;                //第二次相遇时即是环入口节点
            }
        }
        return nullptr;
    }
};