Insert Greatest Common Divisors in Linked List

MEDIUM✓ CHIP-TIMEDLC #2807 — FULL STATEMENT ↗

The drill: Between every pair of neighbouring nodes, splice in a new node holding their greatest common divisor — the original nodes keep their order, just with a gcd node wedged between each original pair.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A singly linked list of positive integers arrives, and the task is to thread a brand-new node between every pair of neighbors already in that list.

Each inserted node holds the greatest common divisor of the two original values sitting immediately on either side of it — the original nodes keep their relative order and their own values untouched; only new nodes get woven in between them.

The result is the same head, now pointing through an alternating chain of original and inserted nodes — original, gcd, original, gcd, and so on — ending on whatever the last original node was.

EX 01

head = [2, 4]

→ [2, 2, 4]

TWO NODES, ONE INSERTION

EX 02

head = [7]

→ [7]

SINGLE NODE, NOTHING TO INSERT

EX 03

head = [9, 6, 3]

→ [9, 3, 6, 3, 3]

GCD SHIFTS AS THE WALK CONTINUES

list length runs from a single node up to a few thousand nodes
node values are positive integers
a list with only one node gets no insertions at all
the returned head is the same list, modified in place

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every new node depends only on two original neighbours, and inserting one never disturbs a pair further down the list — so this can be done in a single left-to-right walk, no lookahead into already-modified structure needed.

HINT 2 THE STRUCTURE

The slow part is usually the gcd itself: counting down from the smaller value and testing divisibility works, but it's a linear scan for a number that Euclid's algorithm collapses to a handful of remainder steps.

HINT 3 ONE STEP FROM THE ANSWER

At each node, compute gcd(node.val, node.next.val) with repeated remainder (a, b) → (b, a mod b) until b hits 0, build a node holding it, splice it in between, then jump past the new node to continue at the original next node.

COACH'S BOARD — THE PATTERN, STEP BY STEP

EUCLID, SPLICED IN PLACEPATTERN · LINKED LIST — SPLICE GCDhead = 9 → 6 → 3

STEP 1

List 9 → 6 → 3. Walk pairs left to right, splicing a new gcd node between each original pair.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/insert-greatest-common-divisors-in-linked-list.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return a

        cur = head
        while cur and cur.next:
            g = gcd(cur.val, cur.next.val)
            node = ListNode(g)
            node.next = cur.next
            cur.next = node
            cur = node.next   # skip past the inserted node to the original next
        return head

TIME O(N · LOG(MAXVAL))SPACE O(1) EXTRAPYTHON · RACE PACE · 15 LN

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd_linear(a: int, b: int) -> int:
            for d in range(min(a, b), 0, -1):   # count down until a shared divisor appears
                if a % d == 0 and b % d == 0:
                    return d
            return 1

        values = []
        node = head
        while node:
            values.append(node.val)
            node = node.next

        merged = []
        for i, v in enumerate(values):
            merged.append(v)
            if i + 1 < len(values):
                merged.append(gcd_linear(v, values[i + 1]))

        dummy = ListNode(0)
        tail = dummy
        for v in merged:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

TIME O(N · MAXVAL)SPACE O(N)PYTHON · TRAINING PACE · 26 LN

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur != null && 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) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

TIME O(N · LOG(MAXVAL))SPACE O(1) EXTRAJAVA · RACE PACE · 17 LN

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = head; node != null; node = node.next) {
            values.add(node.val);
        }

        List<Integer> merged = new ArrayList<>();
        for (int i = 0; i < values.size(); i++) {
            merged.add(values.get(i));
            if (i + 1 < values.size()) {
                merged.add(gcdLinear(values.get(i), values.get(i + 1)));
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : merged) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    private int gcdLinear(int a, int b) {
        for (int d = Math.min(a, b); d >= 1; d--) {
            if (a % d == 0 && b % d == 0) {
                return d;
            }
        }
        return 1;
    }
}

TIME O(N · MAXVAL)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED