Problem statement

You are given the head of a linked list of positive integers. Between every pair of adjacent nodes, insert a new node whose value is the greatest common divisor of those two nodes' values.

Return the head of the list after all insertions. (The greatest common divisor of two numbers is the largest positive integer that divides both of them evenly.)

Example 1

Input: head = [12,18,7,21]
Output: [12,6,18,1,7,7,21]
Explanation: gcd(12, 18) = 6, gcd(18, 7) = 1 and gcd(7, 21) = 7 are inserted between the original pairs.

Example 2

Input: head = [5]
Output: [5]
Explanation: A single node has no adjacent pair, so nothing is inserted.

Example 3

Input: head = [8,8,1000]
Output: [8,8,8,8,1000]
Explanation: gcd(8, 8) = 8 and gcd(8, 1000) = 8.

Constraints

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

Hints for Insert Greatest Common Divisors in Linked List

1. Hint 1

   Each insertion depends only on the two original neighbours, so one pass over the original pairs is enough.

2. Hint 2

   Compute a gcd with Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), ending at gcd(a, 0) = a.

3. Hint 3

   After inserting a node between cur and cur.next, jump straight to the original next node — otherwise you would start pairing the new node with its neighbours.

How to solve Insert Greatest Common Divisors in Linked List

Walk the original nodes; for each node with a successor, splice a new gcd node between them and then step over it to the successor.

Approach

1. Set cur = head.
2. While cur.next exists: create a node with value gcd(cur.val, cur.next.val) pointing at cur.next, link cur.next to it, and move cur to the new node's next (the original successor).
3. Return head.

Why it works

Every original adjacent pair is visited once, before any insertion separates it, and skipping the freshly inserted node keeps it out of the pairing. Euclid's algorithm is correct because any common divisor of a and b also divides a mod b.

Complexity

• Time — O(n log V) — V is the largest value
• Space — O(1) besides the new nodes

Pitfalls

• Advancing to cur.next after the insertion lands on the new gcd node and inserts again, forever growing the list.
• The gcd of equal values is the value itself.

Reference solution

Python

from math import gcd
from typing import Optional

def insertGreatestCommonDivisors(head: Optional[ListNode]) -> Optional[ListNode]:
    cur = head
    while cur.next:
        nxt = cur.next
        cur.next = ListNode(gcd(cur.val, nxt.val), nxt)
        cur = nxt
    return head

Java

static int gcdOf(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return a;
}

public static ListNode insertGreatestCommonDivisors(ListNode head) {
    for (ListNode cur = head; cur.next != null; ) {
        ListNode nxt = cur.next;
        cur.next = new ListNode(gcdOf(cur.val, nxt.val), nxt);
        cur = nxt;
    }
    return head;
}

C++

ListNode* insertGreatestCommonDivisors(ListNode* head) {
    for (ListNode* cur = head; cur->next; ) {
        ListNode* nxt = cur->next;
        cur->next = new ListNode(__gcd(cur->val, nxt->val), nxt);
        cur = nxt;
    }
    return head;
}

JavaScript

var gcdOf = function(a, b) {
    while (b !== 0) { var t = a % b; a = b; b = t; }
    return a;
};

var insertGreatestCommonDivisors = function(head) {
    for (var cur = head; cur.next !== null; ) {
        var nxt = cur.next;
        cur.next = new ListNode(gcdOf(cur.val, nxt.val), nxt);
        cur = nxt;
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium
• Count Special Subsequences Medium