2807. Insert Greatest Common Divisors in Linked List

[mah-shamim]

Discussed in https://github.com/mah-shamim/leet-code-in-php/discussions/515

^{Originally posted by **mah-shamim** September 10, 2024} **Topics:** `Linked List`, `Math`, `Number Theory` 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 1^st diagram denotes the initial linked list and the 2^nd 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 1^st and the 2^nd nodes. - We insert the greatest common divisor of 6 and 10 = 2 between the 2^nd and the 3^rd nodes. - We insert the greatest common divisor of 10 and 3 = 1 between the 3^rd and the 4^th nodes.\ There are no more adjacent nodes, so we return the linked list. **Example 2:**  - **Input:** head = [7] - **Output:** [7] - **Explanation:** The 1^st diagram denotes the initial linked list and the 2^nd diagram denotes the linked list after inserting the new nodes.\ There are no pairs of adjacent nodes, so we return the initial linked list. **Example 3:** - **Input:** cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]] - **Output:** 10 **Constraints:** - The number of nodes in the list is in the range `[1, 5000]`. - `1 <= Node.val <= 1000`

[mah-shamim]

We need to insert nodes between every pair of adjacent nodes in a linked list. The value of the inserted node should be the greatest common divisor (GCD) of the two adjacent nodes' values. We'll traverse the linked list, calculate the GCD for every pair of adjacent nodes, and then insert the new node accordingly.

Here's how you can approach this:

1. Define a ListNode Class: This class will represent each node in the linked list.
2. Traverse the List: We'll iterate through the list to find each pair of adjacent nodes.
3. Insert GCD Nodes: For each pair of adjacent nodes, we'll insert a new node whose value is the GCD of the two adjacent nodes.
4. Return the modified list.

Let's implement this solution in PHP: 2807. Insert Greatest Common Divisors in Linked List

<?php
// Definition for a singly-linked list node.
class ListNode {
    public $val = 0;
    public $next = null;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

/**
 * Function to calculate the GCD of two numbers.
 *
 * @param $a
 * @param $b
 * @return mixed
 */
function gcd($a, $b) {
    if ($b == 0) {
        return $a;
    }
    return gcd($b, $a % $b);
}

/**
 * @param ListNode $head
 * @return ListNode
 */
function insertGreatestCommonDivisors($head) {
    // Edge case: If the list has only one node, return the list as is.
    if ($head == null || $head->next == null) {
        return $head;
    }

    // Start traversing the linked list from the head node.
    $current = $head;

    while ($current != null && $current->next != null) {
        // Calculate GCD of current node's value and the next node's value.
        $gcdValue = gcd($current->val, $current->next->val);

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

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

        // Move to the node after the newly inserted GCD node.
        $current = $gcdNode->next;
    }

    // Return the modified head of the linked list.
    return $head;
}

/**
 * Function to print the linked list for testing purposes.
 * 
 * @param $head
 * @return void
 */
function printList($head) {
    $current = $head;
    while ($current != null) {
        echo $current->val . " ";
        $current = $current->next;
    }
    echo "\n";
}

// Example usage:

// Create the linked list: 18 -> 6 -> 10 -> 3
$head = new ListNode(18);
$head->next = new ListNode(6);
$head->next->next = new ListNode(10);
$head->next->next->next = new ListNode(3);

// Insert GCD nodes.
$modifiedHead = insertGreatestCommonDivisors($head);

// Print the modified linked list.
printList($modifiedHead);

// Output should be: 18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3
?>

Explanation:

1. ListNode Class: This class represents the structure of a node in the linked list, with properties for the value ($val) and the next node ($next).

2. GCD Calculation: The gcd function uses the Euclidean algorithm to compute the greatest common divisor of two integers.

3. Main Logic (insertGreatestCommonDivisors):

   • We loop through the linked list until we reach the second-to-last node.
   • For each pair of adjacent nodes, we compute the GCD of their values.
   • We create a new node with this GCD value and insert it between the current node and the next node.

4. Edge Case: If the list has only one node, we return it as is without making any changes since there are no adjacent nodes.

5. Testing: The function printList is a helper function used to output the values of the linked list for verification.

Time Complexity:

• The time complexity of this solution is (O(n)), where (n) is the number of nodes in the linked list. Calculating the GCD for each adjacent pair takes constant time on average, and we perform a linear traversal of the list.

Example:

For the input list [18, 6, 10, 3], the output is:

18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3