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

2024-01-07 17:23:49

给你一个链表的头?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;
    }
}

文章来源:https://blog.csdn.net/m0_73879453/article/details/135431383
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。