难度: Medium
给你一个链表的头 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运行时间: 40 ms
内存: 19.3 MB
# 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]:
cur = head
while cur.next:
post = cur.next
cur.next = ListNode(gcd(cur.val, post.val))
cur.next.next = post
cur = post
return head
此题解的思路是遍历给定的链表，并在每两个相邻结点之间插入一个新结点。新结点的值是这两个相邻结点的最大公约数（GCD）。为了实现这一点，算法使用Python标凑库中的math.gcd函数来计算两个数的最大公约数。遍历过程中，算法不断更新当前节点，将其指向未处理的下一个节点，直到所有相邻节点都处理完毕。
时间复杂度: O(n)
空间复杂度: O(n)
# 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]:
from math import gcd
cur = head
while cur.next:
post = cur.next
# 计算当前节点和后继节点的最大公约数，并创建新节点
cur.next = ListNode(gcd(cur.val, post.val))
# 将新节点链接到后继节点
cur.next.next = post
# 移动到下一个原始节点处理下一个相邻对
cur = post
return head
在处理链表时，确保原有节点的连接不丢失或不产生环状结构的关键是正确管理节点的 `next` 指针。在插入新节点时，首先应保存当前节点的后继节点（`post = cur.next`），然后将当前节点的 `next` 指向新创建的节点。新节点的 `next` 指针再指向保存的后继节点（`cur.next.next = post`）。这种方法可以保证在插入过程中不会改变原有节点的顺序，也不会创建任何新的循环引用。
是的，在`ListNode`类中应考虑异常处理。特别是当链表为空（`head` 是 `None`）时，应直接返回 `None`，因为没有节点可以处理。当链表只有一个节点时，由于没有后继节点，因此无需插入任何新节点，可以直接返回原始链表。这种情况下的处理可以防止运行时错误，并确保函数的鲁棒性。
在链表的末尾节点，由于没有后继节点，因此无法计算GCD。在这种情况下，最简单的处理方式是不进行任何操作。遍历链表时，当当前节点 (`cur`) 的 `next` 指向 `None`（即没有后继节点）时，循环将终止。因此，末尾节点不会有新的节点插入。
在计算GCD并创建新节点后，直接将新节点链接到后继节点，这种实现方式本身不会显著影响链表的遍历效率。然而，值得注意的是，由于在原始链表中每两个节点之间插入了一个新节点，因此链表的长度增加了近一倍。这意味着对增加后的链表进行遍历所需的时间将比原始链表长。但这与链表的数据结构性质相符，因为链表的遍历时间通常与节点数量成正比。