Insert Greatest Common Divisors in Linked List

Leetcode Problem:

• Insert Greatest Common Divisors in Linked List

Summary

• Inserting greatest common divisors between adjacent nodes in a linked list

Approach

• The approach used is to traverse the linked list and for each pair of adjacent nodes, calculate the greatest common divisor (GCD) using the Euclidean algorithm
• A new node is then inserted between the two nodes with the calculated GCD
• The process is repeated until all nodes have been processed.

Complexity

• O(n), where n is the number of nodes in the linked list

Explain

• The provided C++ code defines a solution to the problem
• The `_gcd` function calculates the GCD of two numbers using the Euclidean algorithm
• The `insertGreatestCommonDivisors` function traverses the linked list, calculates the GCD of each pair of adjacent nodes, and inserts a new node with the calculated GCD between the two nodes
• The process is repeated until all nodes have been processed, resulting in a linked list with the GCDs inserted between adjacent nodes.

Solution Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int _gcd(int a, int b){
        if(a % b == 0) return b;
        return _gcd(b, a%b);
    }
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* ptr = head;
        while(ptr->next != nullptr){
            int a = ptr->val;
            int b = ptr->next->val;
            ListNode* newNode = new ListNode(_gcd(a, b), ptr->next);
            ptr->next = newNode;
            ptr = newNode->next;
        }
        return head;
    }
};