# LC 2807. Insert Greatest Common Divisors in Linked List

### [Problem link](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/)

###### tags: `leedcode` `python` `c++` `medium` `Linked List`

Given the head of a linked list <code>head</code>, in which each node contains an integer value.

Between every pair of adjacent nodes, insert a new node with a value equal to the **greatest common divisor** of them.

Return the linked list after insertion.

The **greatest common divisor** of two numbers is the largest positive integer that evenly divides both numbers.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2023/07/18/ex1_copy.png" style="width: 641px; height: 181px;" />

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1<sup>st</sup> diagram denotes the initial linked list and the 2<sup>nd</sup> diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1<sup>st</sup> and the 2<sup>nd</sup> nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2<sup>nd</sup> and the 3<sup>rd</sup> nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3<sup>rd</sup> and the 4<sup>th</sup> nodes.
There are no more adjacent nodes, so we return the linked list.

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2023/07/18/ex2_copy1.png" style="width: 51px; height: 191px;" />

Input: head = [7]
Output: [7]
Explanation: The 1<sup>st</sup> diagram denotes the initial linked list and the 2<sup>nd</sup> diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.

**Constraints:**

- The number of nodes in the list is in the range <code>[1, 5000]</code>.
- <code>1 <= Node.val <= 1000</code>

## Solution 1 - Linked List
#### Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head

        while cur and cur.next:
            tmp = cur.next
            gcd_node = ListNode(val=math.gcd(cur.val, tmp.val))
            cur.next = gcd_node
            gcd_node.next = tmp
            cur = tmp

        return head

#### C++

/**
 * 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) {
        ListNode *root = head;
        while (root && root->next) {
            int num1 = root->val;
            int num2 = root->next->val;
            int mid_num = gcd(num1, num2);
            ListNode *tmp = root->next;
            root->next = new ListNode(mid_num, tmp);

            root = root->next->next;
        }

        return head;
    }
};

>### Complexity
>n = The number of nodes in the list
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
x