LeetCode 2807. 在链表中插入最大公约数

本文主要是介绍LeetCode 2807. 在链表中插入最大公约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

给你一个链表的头 head ，每个结点包含一个整数值。

在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。

请你返回插入之后的链表。

两个数的 最大公约数 是可以被两个数字整除的最大正整数。

2、接口描述

​

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* insertGreatestCommonDivisors(ListNode* head) {}
};

3、原题链接

2807. 在链表中插入最大公约数

---

二、解题报告

1、思路分析

直接模拟即可

2、复杂度

时间复杂度：O(n) 空间复杂度：O(1)

3、代码详解

​

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {typedef ListNode Node;
public:int gcd(int x , int y){if(x < y) swap(x , y);if(!y) return x;return gcd(y , x % y);}ListNode* insertGreatestCommonDivisors(ListNode* head) {Node* cur = head , *nxt = head -> next;while(cur){nxt = cur -> next;if(nxt)cur -> next = new Node(gcd(cur->val , nxt->val) , nxt);cur = nxt;}return head;}
};

这篇关于LeetCode 2807. 在链表中插入最大公约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---