LeetCode 2807. 在链表中插入最大公约数

给你一个链表的头 head ，每个结点包含一个整数值。

在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的最大公约数。

请你返回插入之后的链表。

两个数的最大公约数是可以被两个数字整除的最大正整数。

示例 1：
在这里插入图片描述
提示：

链表中结点数目在 [1, 5000] 之间。
1 <= Node.val <= 1000

直接模拟即可：

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

        ListNode *curNode = head;
        while (curNode->next)
        {
            int gcd = getGCD(curNode->val, curNode->next->val);
            curNode->next = new ListNode(gcd, curNode->next);
            curNode = curNode->next->next;
        }

        return head;
    }

private:
    int getGCD(int i, int j)
    {
        int k = 0;
        do
        {
            k = i % j;
            i = j;
            j = k;
        } while (k != 0);
  
        return i;
    }
};

如果链表中有n个节点，此算法时间复杂度为O(n)，空间复杂度为O(1)。

求公约数时，可直接使用C++标准库中的__gcd函数，它所在的头文件是algorithm：

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

        ListNode *curNode = head;
        while (curNode->next)
        {
            int gcd = __gcd(curNode->val, curNode->next->val);
            curNode->next = new ListNode(gcd, curNode->next);
            curNode = curNode->next->next;
        }

        return head;
    }
};