insert-greatest-common-divisors-in-linked-list_2807.py

# 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:

# 
# 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:

# 
# 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.

# ---------------------------------------Runtime 110 ms Beats 36.73% Memory 20.9 MB Beats 83.24%---------------------------------------


from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def compute_gcd(self, num1: int, num2: int) -> int:
        while num2:
            num1, num2 = num2, num1 % num2
        return abs(num1)

    def insertGreatestCommonDivisors(
        self, head: Optional[ListNode]
    ) -> Optional[ListNode]:
        root: Optional[ListNode] = head
        while root:
            next_node = root.next
            if next_node:
                gcd_node = ListNode(self.compute_gcd(root.val, root.next.val))
                gcd_node.next = root.next
                root.next = gcd_node
            root = next_node
        return head