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站@灵茶山艾府】 直播讲题，欢迎关注！

---

遍历链表，在当前节点 cur 后面插入 gcd 节点，gcd 节点指向 cur 的下一个节点。

插入后，cur 更新为 cur}.\textit{next}.\textit{next。

循环直到 cur 没有下一个节点为止。

[sol-Python3]

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur.next:
            cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)
            cur = cur.next.next
        return head

[sol-Go]

func insertGreatestCommonDivisors(head *ListNode) (ans *ListNode) {
	cur := head
	for cur.Next != nil {
		cur.Next = &ListNode{gcd(cur.Val, cur.Next.Val), cur.Next}
		cur = cur.Next.Next
	}
	return head
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

复杂度分析

• 时间复杂度：\mathcal{O}(n\log U)，其中 n 为链表长度，U 为节点值的最大值。
• 空间复杂度：\mathcal{O}(1)。返回值的空间不计入，仅用到若干额外变量。