游戏攻略网站开发,app平台开发公司,珠海七中科技制作,重庆短视频培训机构文章目录 题目解题方法复杂度Code Problem: 2807. 在链表中插入最大公约数 题目 给你一个链表的头 head #xff0c;每个结点包含一个整数值。 在相邻结点之间#xff0c;请你插入一个新的结点#xff0c;结点值为这两个相邻结点值的 最大公约数 。 请你返回插入之后的链表。… 文章目录 题目解题方法复杂度Code 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%b0,b就已经是a的最大公约数了我们用a保存了上一次调用的b的值所以a就是我们最终的答案 辗转相除法的证明过程这个老师讲的很好 : https://www.bilibili.com/video/BV1my4y1z7Zn/?spm_id_from333.337.search-card.all.clickvd_sourcef4b0f39061295153d69abcbac1aaa3e6 在插入节点的时候需要判断当前节点和下一个节点是否存在存在则直接插入即可 复杂度
时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def insertGreatestCommonDivisors(self, head: Optional[ListNode]) - Optional[ListNode]:def gcd1(a,b):if b0: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
