南京地区网站开发2019年 2022疫情爆发

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

题目思路

模拟插入流程：

1. 检测当前节点是否有后置结点；
2. 将当前结点与后置结点的值做最大公约数处理得到新结点的值，然后插入到当前结点之后；
3. 再将检测结点向后移动两个位置；
4. 循环123即可；

注意点

计算最大公约数其实有C++自带的__gcd()来实现，不过为了巩固知识也可以选择手写
同时本题的val值在1到1000之间，所以可以这样写一个计算两个整数最大公约数的函数。

int GreatestCommonDivisors(int a, int b) // 1000>=val>=1{if (b == 0) {return a;} else {return GreatestCommonDivisors(b, a % b);}}

这段代码是一个计算两个整数最大公约数的函数，使用了欧几里得算法。

• 函数的参数是两个整数 a 和 b。如果 b 是0，那么返回 a，因为任何数和0的最大公约数都是它自己。如果 b 不是0，那么递归地调用 GreatestCommonDivisors(b, a % b)。
• 这个函数使用了欧几里得算法的思想，递归地计算最大公约数。算法的基本思想是：gcd(a,b)=gcd(b,amod b)。这个过程会持续到b等于0，此时a就是最大公约数。
• 需要注意的是，因为题目的val范围设计在1-1000，所以这个函数没有处理负数的情况，如果输入的 a 和 b 是负数，可能会导致不正确的结果。另外，如果函数被频繁调用，可能会导致栈溢出，因为这是一个递归函数。

Code

/*** 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:int GreatestCommonDivisors(int a, int b) // 1000>=val>=1{if (b == 0) {return a;} else {return GreatestCommonDivisors(b, a % b);}}ListNode* insertGreatestCommonDivisors(ListNode* head) {ListNode* node = head;while (node->next) {node->next = new ListNode(GreatestCommonDivisors(node->val, node->next->val), node->next);node = node->next->next;}return head;}
};