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

发布时间:2024年01月06日

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(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
文章来源:https://blog.csdn.net/qq_51118755/article/details/135428921
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。