Insert Greatest Common Divisors in Linked List

medium linked list math gcd

Problem

Given the head of a linked list, insert between every pair of adjacent nodes a brand-new node whose value is the greatest common divisor (GCD) of those two neighboring values. The GCD of two numbers is the largest integer that divides both of them. Return the head of the modified list.

Inputhead = [18, 6, 10, 3]

Output[18, 6, 6, 2, 10, 1, 3]

gcd(18, 6) = 6, gcd(6, 10) = 2, gcd(10, 3) = 1 — each is spliced between its pair.

list (comma-separated positive integers)

def insert_gcd(head):
    cur = head
    while cur.next:
        a, b = cur.val, cur.next.val
        g = gcd(a, b)
        node = ListNode(g)
        node.next = cur.next
        cur.next = node
        cur = node.next
    return head

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

function insertGcd(head) {
  let cur = head;
  while (cur.next) {
    const g = gcd(cur.val, cur.next.val);
    const node = { val: g, next: cur.next };
    cur.next = node;
    cur = node.next;
  }
  return head;
}

function gcd(a, b) {
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur.next != null) {
            int g = gcd(cur.val, cur.next.val);
            ListNode node = new ListNode(g);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        return head;
    }

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

ListNode* insertGreatestCommonDivisors(ListNode* head) {
    ListNode* cur = head;
    while (cur->next != nullptr) {
        int g = gcd(cur->val, cur->next->val);
        ListNode* node = new ListNode(g);
        node->next = cur->next;
        cur->next = node;
        cur = node->next;
    }
    return head;
}

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

Explanation

The task is purely local: every gap between two neighboring nodes gets one new node dropped into it, and that node's value depends only on the two values on either side. So we never need to look at the whole list at once — we just slide a pointer along and handle one gap at a time.

We keep a single pointer cur. As long as cur has a next node, the pair (cur.val, cur.next.val) defines a gap. We compute their gcd, build a new node holding it, and splice it between them: the new node points to cur.next, then cur.next is rewired to point to the new node.

The one subtlety is where to move next. After inserting, we jump cur to node.next — the original right-hand neighbor — not to the node we just inserted. Skipping over the inserted node prevents us from trying to insert another GCD between the original value and the GCD we just added (which would loop forever).

The GCD itself uses the classic Euclidean algorithm: repeatedly replace (a, b) with (b, a mod b) until b becomes 0; the remaining a is the answer.

Example: [18, 6, 10, 3]. gcd(18, 6)=6 goes between 18 and 6; gcd(6, 10)=2 goes between 6 and 10; gcd(10, 3)=1 goes between 10 and 3. The result is [18, 6, 6, 2, 10, 1, 3].

Time: O(n log M) Space: O(1) extra (excluding inserted nodes)