Insert Greatest Common Divisors in Linked List

We need to implement a function that takes the head of a linked list, and for each pair of adjacent nodes, inserts a new node with a value equal to the greatest common divisor (GCD) of the adjacent nodes’ values.

We’ll iterate through the linked list, and for each pair of nodes, we’ll compute the GCD of their values and insert a new node with that value between them.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from math import gcd

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

        current = head
        while current and current.next:
            # Compute the GCD of the current and next node's values
            common_divisor = gcd(current.val, current.next.val)

            # Create a new node with the computed GCD
            new_node = ListNode(common_divisor)

            # Insert the new node between the current and next nodes
            new_node.next = current.next
            current.next = new_node

            # Move to the next pair of nodes
            current = current.next.next

        return head

This code takes advantage of the gcd function from the math module to compute the greatest common divisor. It then creates a new node with the computed GCD and inserts it between the current pair of nodes. The process is repeated for all adjacent node pairs in the linked list.

Example:

For head = [18,6,10,3], the code would return [18,6,6,2,10,1,3].