2024.1.6力扣每日一题——在链表中插入最大公约数

2024-01-07 23:23:12

2024.1.6

题目来源

力扣每日一题；题序：2807

我的题解

方法一 模拟+数学

正常模拟插入，通过辗转相除法计算出两个节点值之间的最大公约数，然后将其作为新节点插入到两个节点之间

时间复杂度：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);
    }

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

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