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;}
};