Problem of The Day: Insert Greatest Common Divisors in Linked List

Problem Statement

Intuition

The problem involves modifying a linked list by inserting nodes between adjacent nodes based on the greatest common divisor (GCD) of their values. The first thought was to traverse the list while computing the GCD for each consecutive pair of nodes, inserting a new node between them with the GCD as its value.

Approach

1. Traverse the linked list using a while loop.
2. For each pair of adjacent nodes, calculate the GCD of their values.
3. Insert a new node between the two nodes, with the GCD as the node’s value.
4. Continue the process until the end of the list is reached.
5. Return the modified linked list.

Complexity

• Time complexity: The time complexity is \(O(n)\), where \(n\) is the number of nodes in the linked list. This is because we traverse the list once, and each GCD calculation takes constant time.

• Space complexity: The space complexity is \(O(1)\) since we are modifying the list in place and not using any additional data structures, aside from the new nodes being inserted.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def find_gcd(self, a, b):
        while b:
            a, b = b, a % b
        return abs(a)

    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next is None:
            return head
        curr = head
        while curr and curr.next:
            next_node = curr.next
            gcd = self.find_gcd(curr.val, next_node.val)
            curr.next = ListNode(gcd, next_node)
            curr = next_node
        return head

Editorial

Approach: Simulation

class Solution:
    def insertGreatestCommonDivisors(
        self, head: Optional[ListNode]
    ) -> Optional[ListNode]:
        # Helper method to calculate the greatest common divisor using the Euclidean algorithm
        def _calculate_gcd(a, b):
            while b != 0:
                a, b = b, a % b
            return a

        # If the list contains only one node, return the head as no insertion is needed
        if not head.next:
            return head

        # Initialize pointers to traverse the list
        node1 = head
        node2 = head.next

        # Traverse the linked list
        while node2:
            gcd_value = _calculate_gcd(node1.val, node2.val)
            gcd_node = ListNode(gcd_value)

            # Insert the GCD node between node1 and node2
            node1.next = gcd_node
            gcd_node.next = node2

            # Move to the next pair of nodes
            node1 = node2
            node2 = node2.next

        return head