Tag

【迭代】【辗转相除法】【链表】【2024-01-06】

---

题目来源

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

---

解题思路

方法一：迭代

思路

首先需要求两个数的最大公约数，使用辗转相除法。实现代码如下：

// 计算最大公约数
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

还可以直接调用 C++17 标准中引入的 gcd() 函数来计算最大公约数（需要包含头文件 #include ）。有些编译器仲可以使用 __gcd() 来计算最大公约数（需要包含头文件 #include ）。建议直接手写 gcd 也不难。

接着就是在链表的相邻两个节点之间增加一个节点，我们遍历原链表中的每一个节点，在两个相邻的节点之间新增以当前节点值和下一个节点值的最大公约数为值的节点即可。具体实现直接见下方代码即可。

算法

class Solution {
public:
    // 计算最大公约数
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* node = head;
        while(node->next) {
            node->next = new ListNode(gcd(node->val, node->next->val), node->next);
            node = node->next->next;
        }
        return head;
    }
};	

复杂度分析

时间复杂度：$O(nlogU)$，$n$ 为链表中节点的数目，$U$ 是链表节点中的最大值。每次求最大公约数的时间为 $O(logU)$。

空间复杂度：$O(1)$。

---

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。