正常模拟插入，通过辗转相除法计算出两个节点值之间的最大公约数，然后将其作为新节点插入到两个节点之间
时间复杂度：O(nlogU)，logU表示求最大公约数的时间
空间复杂度：O(1)
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode p=head;
ListNode q=head.next;
while(q!=null){
int g_num=gcd(p.val,q.val);
ListNode g=new ListNode(g_num);
g.next=q;
p.next=g;
p=q;
q=q.next;
}
return head;
}
public int gcd(int m,int n){
if(n==0)
return m;
return gcd(n,m%n);
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~