Leet Code POTD: 2807. Insert Greatest Common Divisors in Linked List

To solve the problem “Insert Greatest Common Divisors in Linked List,” the goal is to insert nodes containing the GCD (Greatest Common Divisor) between every pair of nodes in the linked list. Here’s how to approach the solution in JavaScript:

Steps:

1. Find the GCD of two numbers. Use the Euclidean algorithm for calculating the GCD.
2. Traverse the linked list. For each consecutive pair of nodes, insert a new node between them containing the GCD of the two nodes’ values.

Here’s a JavaScript implementation of this:

Solution:

// Helper function to calculate GCD using Euclidean algorithm
function gcd(a, b) {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

// Function to insert GCDs between nodes in the linked list
function insertGCDsInLinkedList(head) {
    if (!head || !head.next) return head; // If the list is empty or has only one node, no change is needed.

    let current = head;
    while (current && current.next) {
        // Find GCD between the current node's value and the next node's value
        let gcdValue = gcd(current.val, current.next.val);

        // Create a new node with the GCD value
        let gcdNode = new ListNode(gcdValue);

        // Insert the GCD node between current and current.next
        gcdNode.next = current.next;
        current.next = gcdNode;

        // Move to the next pair (skip to the node after the inserted one)
        current = gcdNode.next;
    }

    return head;
}

// Helper function to print the linked list
function printLinkedList(head) {
    let current = head;
    while (current) {
        process.stdout.write(current.val + " -> ");
        current = current.next;
    }
    console.log("null");
}

// Example usage:

// Creating a sample linked list: 18 -> 24 -> 36
let head = new ListNode(18, new ListNode(24, new ListNode(36)));

// Insert GCDs
head = insertGCDsInLinkedList(head);

// Print the updated linked list
printLinkedList(head);
// Expected output: 18 -> 6 -> 24 -> 12 -> 36 -> null

Explanation:

• GCD Calculation: The gcd function calculates the GCD using the Euclidean algorithm.
• Linked List Traversal: We iterate through the list and for each pair of nodes, we compute their GCD and insert a new node with that value between them.
• Inserting Nodes: A new node is created for the GCD and inserted between the current node and its next node.
• Example: If the input linked list is 18 -> 24 -> 36, the output will be 18 -> 6 -> 24 -> 12 -> 36.

This approach ensures we modify the linked list by adding the GCD nodes in place.