如何通过C++求出链表中环的入口结点

1. 环的入口结点（题目描述）

给定一个链表，返回链表中环的入口结点。如果链表无环，则返回 NULL。

要求算法的空间复杂度为 O(1)。

2. 思路分析

这道题可以使用双指针法（快慢指针）来解决。

具体的思路为：首先，设定两个指针，分别为 fast 和 slow，然后，让它们以不同的速度往前走（fast 比 slow 快），这样，当两个指针重合时，就表示链表中存在环。

接着，我们需要找到环的入口结点。首先，设集合 S 表示所有从链表头结点到环的入口结点的结点集合，当 slow 和 fast 指针第一次相遇时，fast 指针一定比 slow 指针多走一圈。设链表头结点到环的入口结点的长度为 x，环的周长为 y，则：

1. 当 slow 和 fast 指针相遇时，slow 走过的路程长度为 x + n_1*y，fast 走过的路程长度为 x + n_2*y；
2. 因为 fast 比 slow 快一倍，所以 fast 走过的路程长度是 slow 走过的路程长度的两倍，即：

(x + n_2*y) = 2 * (x + n_1*y)

可化简得：

x = (n_2 - 2 * n_1) * y

接下来，设 a 和 b 分别为 slow 和 fast 指针相遇点到环的入口结点的长度和起点到环的入口结点的长度，则：

1. slow 指针从起点开始的路程长度为 x + a
2. fast 指针从起点开始的路程长度为 x + b

3. 因为 fast 比 slow 快一倍，所以 fast 跑完整个环的时间是 slow 的两倍，所以从相遇点出发的距离等于起点到环入口的距离，即：

   a + y = b

   可以得到以下结论：
   x = (n_2 - 2 * n_1) * y
a + y = b

接下来，我们可以从链表头结点开始，同时移动 slow 和 fast 指针，每次移动一步，当两者相遇时，就表示它们相遇的结点即为环的入口结点。

3. 代码实现及示例说明

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* entryNodeOfLoop(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) {
                fast = head;

                while (fast != slow) {
                    fast = fast->next;
                    slow = slow->next;
                }

                return fast;
            }
        }
        return nullptr;
    }
};

示例1：输入一个带环的链表，请输出该链表的环的入口结点。

1 -> 2 -> 3 -> 4 -> 5 -> 2

期望的输出结果为：2。

示例2：输入一个无环的链表，请输出 NULL。

1 -> 2 -> 3 -> 4 -> 5

期望的输出结果为：NULL。