住房和城乡建设部网站北京网站建设高校

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

题目

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

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

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

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

示例 1：

输入：head = [18,6,10,3] 输出：[18,6,6,2,10,1,3]
解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。

• 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。
• 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。
• 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。 所有相邻结点之间都插入完毕，返回链表。

示例 2：

输入：head = [7] 输出：[7] 解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
没有相邻结点，所以返回初始链表。

提示：

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

解题方法

写一个计算最大公约数的函数，使用辗转相除法计算，当b为0时候，说明上一次调用gcd的时候 a%b=0,b就已经是a的最大公约数了，我们用a保存了上一次调用的b的值，所以a就是我们最终的答案

辗转相除法的证明过程，这个老师讲的很好 :

https://www.bilibili.com/video/BV1my4y1z7Zn/?spm_id_from=333.337.search-card.all.click&vd_source=f4b0f39061295153d69abcbac1aaa3e6

在插入节点的时候需要判断当前节点和下一个节点是否存在，存在则直接插入即可

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:def gcd1(a,b):if b==0:return aa,b = b,a%breturn gcd1(a,b)p = headwhile p and p.next:val = gcd1( p.val , p.next.val) node = ListNode(val,p.next)p.next = nodep = p.next.nextreturn head