# Insert Greatest Common Divisors in Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/insert-greatest-common-divisors-in-linked-list
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Linked List
---
## Problem
Given the head of a linked list `head`, 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:**

![](https://assets.glich.co/dsa/insert-greatest-common-divisors-in-linked-list/image0.png) 

**Input:** head = [18,6,10,3]
**Output:** [18,6,6,2,10,1,3]
**Explanation:** The 1st diagram denotes the initial linked list and the 2nd 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 1st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.

**Example 2:**

![](https://assets.glich.co/dsa/insert-greatest-common-divisors-in-linked-list/image1.png) 

**Input:** head = [7]
**Output:** [7]
**Explanation:** The 1st diagram denotes the initial linked list and the 2nd 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 `[1, 5000]`.
* `1 <= Node.val <= 1000`

# Approaches
## Creating a New List
This straightforward approach involves iterating through the original linked list and building a completely new list that includes the original nodes and the new GCD nodes. It's easier to reason about but uses more memory.
**Time:** O(N * log(K)), where N is the number of nodes in the list and K is the maximum value in a node. The traversal takes O(N) time, and for each of the N-1 pairs, we perform a GCD calculation which takes O(log(K)) time. · **Space:** O(N), where N is the number of nodes in the original list. We create a new list of size `2N - 1`, which requires `O(N)` additional space.
**Pros:** Simple logic, easy to understand and implement.; Preserves the original linked list, which can be an advantage.
**Cons:** Requires O(N) extra space to store the new list, making it less memory-efficient than an in-place solution.
### Explanation
We initialize a new list with a `dummy` head to simplify appending nodes. We then traverse the input list from `head` to tail. For each node we encounter, we first append a copy of it to our new list. Then, we check if this node has a successor in the original list. If it does, we calculate the GCD of the current node's value and its successor's value. A new node containing this GCD is then created and appended to our new list. This process is repeated until all nodes from the original list have been processed. The final result is the list starting from the node after our `dummy` head.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        ListNode current = head;

        while (current != null) {
            // Add the original node
            tail.next = new ListNode(current.val);
            tail = tail.next;

            // If there is a next node, calculate GCD and insert
            if (current.next != null) {
                int gcdVal = gcd(current.val, current.next.val);
                tail.next = new ListNode(gcdVal);
                tail = tail.next;
            }
            current = current.next;
        }

        return dummy.next;
    }

    // Helper function to calculate GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Handle the edge case where the list has 0 or 1 node by returning `head`.
- Create a `dummy` node to serve as the starting point of the new list. A `tail` pointer is used to track the end of the new list.
- Initialize a `current` pointer to the `head` of the original list.
- Iterate while `current` is not `null`:
    - a. Create a new node with `current.val` and append it to the new list: `tail.next = new ListNode(current.val); tail = tail.next;`.
    - b. If `current.next` is not `null`, it means there is an adjacent pair.
        - i. Calculate the GCD of `current.val` and `current.next.val`.
        - ii. Create a new node with the GCD value and append it to the new list: `tail.next = new ListNode(gcd); tail = tail.next;`.
    - c. Advance `current` to the next node in the original list.
- Return `dummy.next`.

## In-place Modification
A more optimal approach in terms of space complexity is to modify the list in-place. We traverse the list, and for each adjacent pair of nodes, we create the new GCD node and insert it between them by rearranging the `next` pointers.
**Time:** O(N * log(K)), where N is the number of nodes in the original list and K is the maximum value in a node. We traverse the original list once, and each step involves a GCD calculation. · **Space:** O(1). We modify the list in-place. The space for the new nodes is part of the output structure and is not considered extra auxiliary space. The only extra space is for a few pointers and variables, which is constant.
**Pros:** Extremely space-efficient, using only O(1) auxiliary space.; Avoids the overhead of allocating an entire new list.
**Cons:** Modifies the input list, which might be a side effect to avoid in some applications.
### Explanation
We traverse the list with a pointer, let's call it `current`, starting at the `head`. The loop continues as long as `current.next` is not null, ensuring we can always form a pair `(current, current.next)`. In each iteration, we first get a handle on the node after `current`, let's call it `nextNode`. Then, we compute the GCD of `current.val` and `nextNode.val`. A new node is created with this GCD value. This new node is inserted between `current` and `nextNode` by setting `current.next` to the new node, and the new node's `next` to `nextNode`. Finally, to proceed to the next pair of *original* nodes, we advance `current` to `nextNode`. The process repeats until the end of the list is reached.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode current = head;
        while (current.next != null) {
            ListNode nextNode = current.next;
            
            // Calculate GCD
            int gcdVal = gcd(current.val, nextNode.val);
            
            // Create and insert the new node
            ListNode newNode = new ListNode(gcdVal);
            newNode.next = nextNode;
            current.next = newNode;
            
            // Move to the next original node
            current = nextNode;
        }
        
        return head;
    }

    // Helper function to calculate GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- Initialize a pointer `current = head`.
- If the list is empty or has only one node, no insertions are needed, so return `head`.
- Iterate through the list with the condition `while (current.next != null)`:
    - a. Store the reference to the next node: `nextNode = current.next`.
    - b. Calculate the GCD of `current.val` and `nextNode.val`.
    - c. Create a new `ListNode` with the GCD value.
    - d. Rewire the pointers to insert the new node: `current.next = newNode` and `newNode.next = nextNode`.
    - e. Move `current` to the next node of the *original* list to process the next pair: `current = nextNode`.
- Return the original `head`, which now points to the modified list.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode insertGreatestCommonDivisors ( ListNode head ) { for ( ListNode pre = head , cur = head . next ; cur != null ; cur = cur . next ) { int x = gcd ( pre . val , cur . val ); pre . next = new ListNode ( x , cur ); pre = cur ; } return head ; } private int gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ); } }
```

### CPP

```cpp
/** * 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 * pre = head ; for ( ListNode * cur = head -> next ; cur ; cur = cur -> next ) { int x = gcd ( pre -> val , cur -> val ); pre -> next = new ListNode ( x , cur ); pre = cur ; } return head ; } };
```

### Python

```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 ]: pre , cur = head , head . next while cur : x = gcd ( pre . val , cur . val ) pre . next = ListNode ( x , cur ) pre , cur = cur , cur . next return head
```