LeetCode.每日一题.10(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

解题思路：

? ? ? ? 定义一个指针指指向头结点，取该指针指向节点只与下一节点的最大公约数，创建新的节点，将最大公约数赋给新的节点，让新节点的next指向p的next，指针p的next指向新节点，再让p指向next的next，往复下去直到指针p的next等于null。

代码实现：

C语言实现：

struct ListNode* insertGreatestCommonDivisors(struct ListNode* head){
    //返回只有一个节点的链表
    if(!head->next){
        return head;
    }
    //定义指针p
    struct ListNode *p=head;
    while(p->next){
        //取最大公约数
        int a=p->val,b=p->next->val,c;
        while(b!=0){
            c=a%b;
            a=b;
            b=c;
        }
        //插入新节点
        struct ListNode *newnode=(struct ListNode*)malloc(sizeof(struct ListNode));
        newnode->val=a;
        newnode->next=p->next;
        p->next=newnode;
        p=newnode->next;
    }
    return head;
}

java实现：

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        //返回只有一个节点的链表
        if(head.next==null) return head;
        //定义指针p
        ListNode p=head;
        //循环遍历链表
        while(p.next!=null){
            //指针p的next指向新节点，该节点值为commondivisors返回值
            p.next=new ListNode(commondivisors(p.val,p.next.val),p.next);
            p=p.next.next;
        }
        return head;
    }
    //求最大公约数
    public int commondivisors(int val1,int val2){
        while(val1!=0){
            int n=val2%val1;
            val2=val1;
            val1=n;
        }
        return val2;
    }
}