【leetcode 2807. 在链表中插入最大公约数】链表插入 & 辗转相除法（欧几里得法） & C++中的gcd

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

题目描述

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

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

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

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

思路

这道题目本身是比较简单的，主要是考察两个点：

• 按要求在链表中插入新节点
• 计算最大公约数

在链表中插入新节点

在链表中插入新节点，主要是通过修改节点的next，只要注意修改顺序，还是比较简单的。

ListNode *p = head;
while(p->next) {
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->next = p->next;
    p->next = newNode;
    p = newNode->next;
}

或者更简洁的：

ListNode *p = head;
while (p->next) {
    p->next = new ListNode(0, p->next);
    p = p->next->next;
}

最大公约数计算

最大公约数的计算，我们在中小学阶段就学过了，就是利用辗转相除法，国外称为欧几里得法 Euclid’s algorithm。

辗转相除法

辗转相除法的思路比较简单：

两个数的最大公约数等于其中较小的数字和二者之间余数的最大公约数

用代码表示的话，就是：

gcd(a,b) = gcd(b,a mod b)

实现起来也就比较简单了：

递归

int GCD(int a, int b) {
    int r = a % b;
    if(r) {
        return GCD(b, r);
    }
    return b;
}

迭代

int GCD(int a, int b) {
    while(b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

其他求最大公约数的算法

除了辗转相除法，还有其他算法可以用来计算最大公约数，比如：

• 更相减损术
• stein算法

具体可以参考文章

C++17内置的gcd vs. __gcd

C++17标准库中内置了求最大公约数的函数：gcd，使用需要引入头文件<numeric>，并且在编译时制定C++17标准。

在引入头文件<numeric>后，其实有两个函数可以用来计算最大公约数，另一个就是__gcd()，但文档中并没有提及这个函数，gcd和__gcd的区别可以参考stackoverflow中的回答，懒人版答案：

__gcd是内置函数，没打算给外面用，这也是文档中没有提及的原因。所以更推荐使用gcd

ps：如果大家尝试一下会发现__gcd要求参数都是unsigned int，否则编译时会报错：

.../c++/v1/__numeric/gcd_lcm.h:53:5: error: static_assert failed due to requirement '!is_signed<int>::value' ""
    static_assert((!is_signed<_Tp>::value), "");
    
test_gcd.cpp:11:15: note: in instantiation of function template specialization 'std::__gcd<int>' requested here
    int res = __gcd(a, b);

1 error generated.

最终代码

/**
 * 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) {
        ListNode *p = head;
        while(p->next) {
            ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
            newNode->val = gcd(p->val, p->next->val);
            newNode->next = p->next;
            p->next = newNode;
            p = newNode->next;
        }
        return head;
    }
};