2807. Insert Greatest Common Divisors in Linked List

Description

Given a singly linked list, you are required to insert a node with the greatest common divisor (GCD) of two consecutive node values between every two adjacent nodes. This will modify the list in such a way that for each pair of consecutive nodes, a new node is inserted with the value of the GCD of their values.

Intuition

To solve this problem, we can calculate the GCD of two consecutive nodes in the linked list and insert a new node with this GCD value in between them. We iterate through the list and apply this process until we reach the end of the list.

The GCD of two numbers is the largest number that divides both numbers without leaving a remainder. We can compute the GCD either through iterative or recursive approaches.

Approach

1. Helper Function for GCD: We create a helper function to compute the GCD of two numbers. This can be done by iterating through all numbers from 2 to the smaller of the two numbers and checking which is the largest divisor common to both.
2. Iterating Through the List: We traverse the linked list starting from the head. For each pair of consecutive nodes, we compute their GCD and insert a new node with this value between the two nodes.
3. Insertion: After computing the GCD for a pair of nodes, we create a new node with the GCD value and adjust the next pointers to insert the node between the current node and the next node.
4. Repeat: We continue this process until the end of the list, modifying the list in place by adding new nodes.

Complexity

Time Complexity:

• Calculating the GCD between two numbers takes O(min(a, b)) where a and b are the two numbers.
• For a linked list of n nodes, we perform this operation n - 1 times (once between each consecutive pair of nodes). Therefore, the time complexity is O(n * min(a, b)), where n is the number of nodes in the list.

Space Complexity:

• The space complexity is O(1) if we ignore the space used by the new nodes. The algorithm works in-place, but additional nodes are created, which leads to a space usage proportional to the size of the new nodes added.
• Including the new nodes, the space complexity would be O(n) where n is the number of original nodes, as each insertion creates an additional node.

Code

C++

class Solution {
public:
    int findGCD(int num1, int num2) {
        int smaller = std::min(num1, num2);
        int maxGCD = 1;

        for (int i = 2; i <= smaller; i++) {
            if (num1 % i == 0 && num2 % i == 0) {
                maxGCD = i;
            }
        }
        return maxGCD;
    }

    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* curr = head;

        while (curr->next != nullptr) {
            ListNode* next = curr->next;
            int gcd = findGCD(curr->val, next->val);
            curr->next = new ListNode(gcd, next);
            curr = curr->next->next;
        }
        return head;
    }
};

Python

class Solution:
    def findGCD(self, num1, num2):
        smaller = min(num1, num2)
        max_gcd = 1

        for i in range(2, smaller + 1):
            if num1 % i == 0 and num2 % i == 0:
                max_gcd = i

        return max_gcd

    def insertGreatestCommonDivisors(self, head):
        curr = head

        while curr.next:
            next_node = curr.next
            gcd = self.findGCD(curr.val, next_node.val)
            curr.next = ListNode(gcd, next_node)
            curr = curr.next.next

        return 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 {
    private int findGCD(int num1, int num2) {
        int smaller = Math.min(num1, num2);
        int maxGCD = 1;

        for (int i = 2; i <= smaller; i++) {
            if (num1 % i == 0 && num2 % i == 0) {
                maxGCD = i;
            }
        }
        return maxGCD;
    }

    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode curr = head;

        while (curr.next != null) {
            ListNode next = curr.next;
            int gcd = findGCD(curr.val, next.val);
            curr.next = new ListNode(gcd, next);
            curr = curr.next.next;
        }
        return head;
    }
}

JavaScript

var insertGreatestCommonDivisors = function (head) {

    let findGCD = function (num1, num2) {
        let smaller = Math.min(num1, num2)
        let max = 1

        for (let i = 2; i <= smaller; i++) {
            if (num1 % i === 0 && num2 % i === 0) {
                max = i
            }
        }
        return max
    }

    let curr = head

    while (curr.next) {
        let next = curr.next
        let gcd = findGCD(curr.val, next.val)
        curr.next = new ListNode(gcd, next)
        curr = curr.next.next
    }
    return head
}