题解 | #牛牛的冒险旅程#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  private:
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return int整型
     */
    int gcdInCycle(ListNode* head) {
        // write code here
        if (!head || !head->next) {
            cout << "too short" << endl;
            return -1;
        }
        ListNode* slow = head, *fast = head;

        // 快慢指针检测环
        // 这道题比较特殊，题目里明确说明每个节点的值是唯一的，也就是输入里相同值就表示同一个节点
        // 追及问题，速度差是一个 next，
        // 追及路程是 一个环，快指针套圈多走一个环
        do {
            if (!fast || !fast->next) {
                cout << "no ring" << endl;
                return -1;
            }
            slow = slow->next;
            fast = fast->next->next;
        } while (fast && fast->val && slow->val != fast->val);
        // cout << slow->val << " " << fast->val << endl;
        // 外面还要多判断一次是防止 fast = fast->next->next 之后
        // 取到 nullptr，这种情况下 fast->val 什么都没有就直接段错误了
        if (!fast || !fast->next) {
            cout << "no ring" << endl;
            return -1;
        }
        // 找到环的入口
        // 相同时间内，上面的快指针速度是慢指针两倍，路程也是慢指针两倍
        // 且已知快指针比慢指针多走一个环，可推出慢指针只走了一个环的路程
        // 而且根据题目的特殊性，每个节点的值是唯一的，重复值意味着同一个节点
        // 成环的部分值只需要循环最多三次（举个例子，在入口相遇，
        // 慢指针可能不在第一个循环的入口，快指针又要比慢指针多走一个环）
        // 链表里面前面有一段是没有成环的，
        // 可以推出慢指针在环里面被追上的位置就是环长度减去前面这一段路程
        // 换句话说，慢指针只需要再多走这一段，就能走到环的入口
        // 下面的程序正是利用这一点，两个指针没有速度差，相遇正好在环的入口处
        ListNode* start = head;
        while (start->val != slow->val) {
            start = start->next;
            slow = slow->next;
        }
        // cout << start->val << endl;

        // 计算环中所有节点的值的最大公约数
        // 还是要注意这道题的特殊性，每个节点的值是唯一的，重复值表示同一个节点
        int result = start->val;
        ListNode* ringNode = start->next;
        while (ringNode->val != start->val) {
            result = gcd(result, ringNode->val);
            ringNode = ringNode->next;
        }

        return result;
    }
};