LeetCode.每日一题.10(2807.在链表中插入最大公约数)

本文主要是介绍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;}//定义指针pstruct 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;//定义指针pListNode 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;}
}