建设网站要注册公司吗,wordpress伪静态化,seo关键词排名优化方法,商城推广方案给你一个链表的头 head #xff0c;每个结点包含一个整数值。
在相邻结点之间#xff0c;请你插入一个新的结点#xff0c;结点值为这两个相邻结点值的 最大公约数 。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。
示例 1#xf…给你一个链表的头 head 每个结点包含一个整数值。
在相邻结点之间请你插入一个新的结点结点值为这两个相邻结点值的 最大公约数 。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。
示例 1 提示
链表中结点数目在 [1, 5000] 之间。 1 Node.val 1000
直接模拟即可
/*** 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) {if (head nullptr){return nullptr;}ListNode *curNode head;while (curNode-next){int gcd getGCD(curNode-val, curNode-next-val);curNode-next new ListNode(gcd, curNode-next);curNode curNode-next-next;}return head;}private:int getGCD(int i, int j){int k 0;do{k i % j;i j;j k;} while (k ! 0);return i;}
};如果链表中有n个节点此算法时间复杂度为O(n)空间复杂度为O(1)。
求公约数时可直接使用C标准库中的__gcd函数它所在的头文件是algorithm
/*** 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) {if (head nullptr){return nullptr;}ListNode *curNode head;while (curNode-next){int gcd __gcd(curNode-val, curNode-next-val);curNode-next new ListNode(gcd, curNode-next);curNode curNode-next-next;}return head;}
};
