🔗 🟡 2807. Insert Greatest Common Divisors in Linked List 1279

tags: `Biweekly Contest 110` `鏈結串列(Linked List)` `數學(Math)` `數論(Number Theory)`

題意

給定一個鏈結串列的頭節點 $head$ ，其中每個節點包含一個整數值。

在每對相鄰節點之間，插入一個新節點，其值等於這兩個節點值的 最大公約數(Greatest Common Divisor, GCD)，其中兩個數的最大公約數是能夠整除這兩個數的最大正整數。

返回插入後的鏈結串列。

約束條件

鏈結串列中節點數目在 $[1, 5000]$ 之間。
每個節點的值在 $[1, 1000]$ 之間。

思路：模擬(Simulation)

由於題目要求在每對相鄰節點之間插入一個新節點，因此我們需要遍歷整個鏈結串列，並在每對相鄰節點之間插入一個新節點。

使用一個變數 $cur$ 指向當前節點。由於題目保證了必存在至少一個節點，因此我們只需要檢查下一個節點 $cur.next$ 是否存在即可。

將 $cur$ 指向的節點與 $cur.next$ 指向的節點的最大公約數插入到 $cur$ 與 $cur.next$ 之間，並將新節點的下一個節點指向 $cur.next$ 。但需注意，此時 $cur.next$ 已經指向新插入的節點，故在將 $cur$ 移動到下一個節點時，需要將其移動到 $cur.next.next$ ，才是在原本的鏈結串列中的下一個節點。

由於頭節點不會被修改或刪除，最後返回頭節點 $head$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 是鏈結串列中節點的數目。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head # 當前節點
        while cur.next is not None: # 由於要在每兩個節點之間插入新的節點，所以需要檢查 cur.next 是否存在
            cur.next = ListNode(math.gcd(cur.val, cur.next.val), cur.next) # 插入新的節點
            cur = cur.next.next # 移動到下一個節點
        return head # 返回頭節點

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* cur = head;
        while (cur->next != nullptr) {
            cur->next = new ListNode(gcd(cur->val, cur->next->val), cur->next);
            cur = cur->next->next;
        }
        return head;
    }
};