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.

Examples

Example 1:

---
title: Input List
---

 graph LR
   A18[18] --> B6[6] --> C10[10] --> D3[3]
  
---
title: Output List
---

 graph LR
   A18[18] --> B6[6]:::gcd_node --> E6[6] --> F2[2]:::gcd_node --> C10[10] --> G1[1]:::gcd_node --> D3[3]

classDef gcd_node fill:#1E90FF,stroke:#000,stroke-width:2px;
  
1
2
3
4
5
6
7

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:

1
2
3
4

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.

Solution

Method 1 - Using curr and next node

Here are the steps:

  1. GCD Calculation:
    • Implement the gcd function using the Euclidean algorithm to compute the greatest common divisor of two integers.
  2. Traverse the Linked List:
    • Use a pointer current to traverse the linked list.
    • For each pair of adjacent nodes (current and current.next), calculate the GCD.
  3. Insert New Node:
    • Create a new node with the GCD value.
    • Adjust the next pointers to insert the new node between current and current.next.
    • Move the pointer current to nextNode to continue traversal.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode curr = head;
        while (curr != null && curr.next != null) {
            ListNode next = curr.next;
            int gcdVal = gcd(curr.val, next.val);

            // Create new node with the GCD value
            ListNode gcdNode = new ListNode(gcdVal);
            gcdNode.next = next;
            curr.next = gcdNode;

            // Move to the next pair
            curr = next;
        }

        return head;
    }
    // Method 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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def gcd(self, a: int, b: int) -> int:
        while b:
            a, b = b, a % b
        return a

    def insertGreatestCommonDivisors(
        self, head: Optional[ListNode]
    ) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        curr = head
        while curr and curr.next:
            next = curr.next
            gcd_val = self.gcd(curr.val, next.val)

            # Create new node with the GCD value
            gcd_node = ListNode(gcd_val)
            gcd_node.next = next
            curr.next = gcd_node

            # Move to the next pair
            curr = next

        return head

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Each node is visited once, and the GCD calculation adds a negligible amount of additional time per node.
  • 🧺 Space complexity: O(1), additional space, not counting the space used by the new nodes created and the input/output linked list.