leetcode-142. 环形链表 II

环形链表三连问：

1. 是否有环 141

2. 找出环的入口 142

3. 环中节点个数

如何计算环中节点个数?

idx1和idx2相遇在环的入口, 让idx2单独在环里再走一圈, 并进行计数, 当idx2→next == idx1时, 返回count+1, 就是所谓的环中节点的个数

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;

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

            int cnt = 1; // 记录环中节点个数, 最初节点个数为1

            if (fast == slow)
            {
                // 找到相遇节点
                ListNode* idx1 = head;
                ListNode* idx2 = fast;
                while (idx1 != idx2)
                {
                    idx1 = idx1->next;
                    idx2 = idx2->next;
                }

                // 3 记录环中节点个数
                while (idx2->next != idx1)
                {
                    cnt++;
                    idx2 = idx2->next;
                }

                cout << cnt << endl;
                // 如果idx1=idx2，就是环的入口
                return idx1;
            }
        }
        // 链表无环返回NULL
        return NULL;
    }
};

1 如何判断有环 2 环内相遇点 3 环的入口点

最重要的就是找到环的入口，

数学证明：

把环形链表分为三部分

• 头节点—-》环的入口节点 的节点数是 x
• 环入口节点—》环内相遇节点 的节点数量是 y
• 相遇节点—》环入口节点 的节点数量是z

快慢指针：

fast指针每次走2步，slow指针每次走1步

当fast和slow指针相遇的时候，因为slow指针走的慢，所以走了x+y个节点；

fast指针走的快，所以肯定会追上slow指针，所以一共走了 x+y + n(y+z)个节点；fast指针肯定要在环中多走几圈才能追上slow指针；

又因为fast指针走的步数是slow指针的2倍；

所以有 2*slow走的步数 = fast走的步数，

即 2*(x+y) = x+y + n(y+z)，

化简得：

x+y = n(y+z)，拆出来一个y+z，则有

x + y = (n-1)*(y+z) + y + z

x = (n-1)(y+z) + z，其中n ≥ 1

当n=1，时，有 x = z ;

即 下面2个节点数是相同的

• 头节点—-》环的入口节点 的节点数是 x
• 相遇节点—》环入口节点 的节点数量是z

因此，头节点位置是已知的，先找到快慢指针的相遇节点，

然后分别从头节点和相遇节点向下走1步，相遇的节点就是 环的入口节点。

先找到快慢指针相遇的节点，然后分别从头节点和相遇节点向前走，2指针相遇的地方，就是环的入口

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 本题和 141 的区别，需要 返回链表开始入环的第一个节点

        // 字节-判断是否有环，并打印首尾节点
        // 写了个快慢指针，问能不能再优化
        // x,y,z , 证明出 x = z就行 
        // idx1从头节点出发，idx2从相遇节点出发，然后各自每次走1步，相遇的节点就是环的入口节点

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

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

            if (fast == slow)
            {
                // 找到相遇节点
                ListNode* idx1 = head;
                ListNode* idx2 = fast;
                while (idx1 != idx2)
                {
                    idx1 = idx1->next;
                    idx2 = idx2->next;
                }

                // 如果idx1=idx2，就是环的入口
                return idx1;
            }
        }
        // 链表无环返回NULL
        return NULL;
    }
};