題目

2807. Insert Greatest Common Divisors in Linked List
難度: 中等偏易

題意

給定一串聯鏈結head，在相鄰的兩個節點中，插入新的節點，值為兩個節點值的最大公因數。

方向

遍歷head，若目前節點擁有下一個節點，則創建一個新節點，填入最大公因數，新節點的下一個指標指向目前節點的下一個節點，目前節點的下一個指標指向新節點。
(簡單到不知道要擠什麼內容出來)

GCD特性:
https://hackmd.io/@sysprog/gcd-impl

實作

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* curr = head;
        while(curr)
        {
            if(curr->next)
            {
                ListNode* insert = new ListNode(gcd(curr->val, curr->next->val), curr->next);
                curr->next = insert;
                curr = curr->next;
            }
            curr = curr->next;
        }
        return head;
    }
};

分析

若head長度為N
時間複雜度: O(N)，遍歷head長度為N
空間複雜度: O(N)，建立N - 1個新節點

結果

Accepted
582/582 cases passed (35 ms)
Your runtime beats 79.23 % of cpp submissions
Your memory usage beats 49.64 % of cpp submissions (35.6 MB)