题目描述
给你一个链表的头 head
,每个结点包含一个整数值。
在相邻结点之间,请你插入一个新的结点,结点值为这两个相邻结点值的 最大公约数。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。
样例
输入:head = [18,6,10,3]
输出:[18,6,6,2,10,1,3]
解释:第一幅图是一开始的链表,第二幅图是插入新结点后的图(蓝色结点为新插入结点)。
- 18 和 6 的最大公约数为 6,插入第一和第二个结点之间。
- 6 和 10 的最大公约数为 2,插入第二和第三个结点之间。
- 10 和 3 的最大公约数为 1,插入第三和第四个结点之间。
所有相邻结点之间都插入完毕,返回链表。
输入:head = [7]
输出:[7]
解释:第一幅图是一开始的链表,第二幅图是插入新结点后的图(蓝色结点为新插入结点)。
没有相邻结点,所以返回初始链表。
限制
- 链表中结点数目在
[1, 5000]
之间。 1 <= Node.val <= 1000
算法
(模拟) $O(n \log m)$
- 按顺序遍历链表,每次拿到当前节点和下一个节点的地址,然后插入最大公约数。
时间复杂度
- 遍历链表一次,每个节点都需要 $O(\log m)$ 的时间计算最大公约数,故时间复杂度为 $O(n \log m)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储新节点。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* insertGreatestCommonDivisors(ListNode* head) {
ListNode *p1 = head, *p2 = head->next;
while (p2) {
int g = gcd(p1->val, p2->val);
p1->next = new ListNode(g, p2);
p1 = p2;
p2 = p2->next;
}
return head;
}
};