EASY

2807. Insert Greatest Common Divisors in Linked List

You are given the head of a linked list of positive integers. Between every two consecutive nodes, insert a new node whose value is the greatest common divisor (GCD) of the two nodes.

Return the head of the modified linked list.

Example

Input:

head = [18,6,10,3]

Output:

[18,6,6,2,10,1,3]

Explanation: - Insert GCD(18,6)=6 between 18 and 6 - Insert GCD(6,10)=2 between 6 and 10 - Insert GCD(10,3)=1 between 10 and 3

Constraints

The number of nodes in the list is in the range [1, 1000].
1 ≤ Node.val ≤ 1000

Solution: Linked List Traversal

Time Complexity: O(n), where n is the number of nodes.
Space Complexity: O(1), in-place modification.

C++

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