LC 2807.Insert Greatest Common Divisors in Linked List
本文最后更新于:1 年前
题目描述
这是 LeetCode
上的 2807. 在链表中插入最大公约数 ,难度为中等。
给你一个链表的头 head
,每个结点包含一个整数值。
在相邻结点之间,请你插入一个新的结点,结点值为这两个相邻结点值的 最大公约数 。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。
示例 1:
1 |
|
示例 2:
1 |
|
提示:
- 链表中结点数目在
[1, 5000]
之间。 1 <= Node.val <= 1000
解答
方法一:模拟
根据题目要求,遍历一次链表,分别记录前后的两个结点,计算出两个结点的最大公约数并插入中间即可。
1 |
|
时间复杂度:
,其中n
表示链表结点的数目,U
表示链表结点中的最大值,每次求最大公约数的花费时间为 ,需要遍历整个链表,总的时间复杂度为 。空间复杂度:
,返回值不计入空间复杂度中。
每题一图
LC 2807.Insert Greatest Common Divisors in Linked List
https://chen-huaneng.github.io/2024/01/06/2024-01-06-2024-01-06-lc-2807/
Powered By Valine
v1.5.1
v1.5.1