It’s a medium problem with the description being:

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.

Constraints:

The number of nodes in the list is in the range [1, 5000].

1 <= Node.val <= 1000

For this problem first thing to understand is that you need to know how to get the greatest common divisor.

An easy way to do would be use what’s already written through BigInteger gcd method:

public BigInteger gcd(BigInteger val)

Returns a BigInteger whose value is the greatest common divisor of abs(this) and abs(val). Returns 0 if this == 0 && val == 0.

With that in hand, as the problem states you need to add new node in between the two nodes being calculated.

Also since we don’t know how many nodes we have, we will have to loop indefinitely and once there is no next node we assume the loop is over.

Wrapping up those ideas in mind, the solution proposed would be:

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode pivot = head;
        while(true) {
            if(Objects.isNull(pivot.next)){
                return head;
            }
            ListNode next = pivot.next;
            int gcd = getGreatestCommonDivisor(pivot.val, next.val);
            ListNode newNode = new ListNode(gcd, next);
            pivot.next = newNode;
            pivot = next;
        }
    }

    // Greatest Common Divisor from BigInteger class
    private int getGreatestCommonDivisor(int a, int b) {
        return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
    }
}

Runtime: 16ms, faster than 19.39% of Java online submissions.

Memory Usage: 45.45 MB, less than 19.34% of Java online submissions.

That’s a good solution, but still takes a lot of time to get it sorted out.

In this case we could remove some instances references and also use a more primitive way of calculating the greatest common divisor, and with that achieve a 1ms runtime:

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode pivot = head;
        while(true) {
            if(pivot.next==null){
                return head;
            }
            ListNode next = pivot.next;
            pivot.next = new ListNode(getGreatestCommonDivisor(pivot.val, next.val), next);
            pivot = next;
        }
    }

    // Greatest Common Divisor from BigInteger class
    private int getGreatestCommonDivisor(int a, int b) {
         while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Runtime: 1ms, faster than 100.00% of Java online submissions.

Memory Usage: 45.16 MB, less than 54.56% of Java online submissions.

—

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)