2807. Insert Greatest Common Divisors in Linked List. Rust, C++

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 1st diagram denotes the initial linked list and the 2nd 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 1st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.        

Example 2:

Input: head = [7]
Output: [7]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.        

Constraints:

• The number of nodes in the list is in the range [1, 5000].
• 1 <= Node.val <= 1000

Approach. Linear traverse of LL

Complexity

• Time: C++17 std::gcd() = log(min(a, b))
• Space: O(n+n-1). n nodes. n-1 new nodes inserted in between

Code

CPP

/**
 * 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:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* origHead = head;
        while (head->next != nullptr) {
            // Calculate HCF or GCD using c++ inbuild function available
            // in #include<numeric> C++17
            int g = gcd (head->val, head->next->val);

            // Allocate new node
            ListNode* newNode = new ListNode(g);

            // Point newNode->next = head->next
            // And point head to newNode
            newNode->next = head->next;
            head->next = newNode;

            // Now move to next node of original list
            head = newNode->next;
        }
        return origHead;
    }
};        

Rust

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    /*
        Pointer is represented as Option<Box>
        int *x
        x: Option<Box<i32>>
    */
    pub fn insert_greatest_common_divisors(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // Save head, we will return it
        let mut current = &mut head;

        // Until node is not null
        while let Some(ref mut node) = current {

            // if node.next has Some value
            if let Some(ref mut next_node) = node.next {

                // GCD or HCF using Euclid Method
                use std::cmp::min;
                fn gcd(mut a: i32, mut b: i32) -> i32 {
                    while b != 0 {
                        let temp = b;
                        b = a % b;
                        a = temp;
                    }
                    a
                }

                // Create new ListNode with the calculated GCD
                let new_node = Some(Box::new(ListNode {
                    val: gcd(node.val, next_node.val),  //gcd(present, next)
                    next: node.next.take(),     //point new node to next of present
                }));

                // Point current node's next to the new node
                node.next = new_node;

                // Move to the next node in the original list
                current = &mut node.next.as_mut().unwrap().next;
            } else {
                break;
            }
        }

        head
    }
}        

Rust vs C++