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

简介: leetcode2807.在链表中插入最大公约数

题目

给你一个链表的头 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(n)O(n)

空间复杂度:

O ( 1 ) O(1)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 a
            a,b = b,a%b
            return gcd1(a,b)
        p = head
        while p and p.next:
            val = gcd1( p.val , p.next.val) 
            node = ListNode(val,p.next)
            p.next = node
            p = p.next.next
        return head


目录
相关文章
|
4天前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
4天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
14 4
|
4天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
10 0
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点
|
4天前
|
C++
[leetcode 链表] 反转链表 vs 链表相交
[leetcode 链表] 反转链表 vs 链表相交
|
4天前
【力扣】148. 排序链表
【力扣】148. 排序链表
|
4天前
|
索引
【力扣】142. 环形链表 II
【力扣】142. 环形链表 II
|
4天前
【力扣】19. 删除链表的倒数第 N 个结点
【力扣】19. 删除链表的倒数第 N 个结点
|
4天前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表