How to Insert GCD Nodes into a Linked List – Step-by-Step Java Solution

A recent anecdote shows a company that fired its high‑paid technical director to cut costs, only to see the entire R&D department collapse and later pay double to rehire, highlighting that true value differs from mere cost.

Problem: Insert GCD Between Adjacent Nodes in a Singly Linked List

Given a singly linked list whose node values are integers (positive, zero, or negative), insert a new node between every pair of adjacent nodes whose value is the greatest common divisor (GCD) of the two original values. For example, 18→6→10 becomes 18→6→6→2→10.

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int v) { this.val = v; }
    ListNode(int v, ListNode n) { this.val = v; this.next = n; }
}

public class InsertGCDInLinkedList {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            int a = cur.val, b = cur.next.val;
            int g = gcd(a, b);
            ListNode mid = new ListNode(g);
            // insert between cur and cur.next
            mid.next = cur.next;
            cur.next = mid;
            // move to the original next node
            cur = mid.next;
        }
        return head;
    }

    // Euclidean algorithm, works with 0 and negative numbers
    private int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        if (a == 0) return b;
        if (b == 0) return a;
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    // simple test
    public static void main(String[] args) {
        ListNode n3 = new ListNode(10);
        ListNode n2 = new ListNode(6, n3);
        ListNode n1 = new ListNode(18, n2);
        InsertGCDInLinkedList s = new InsertGCDInLinkedList();
        ListNode h = s.insertGreatestCommonDivisors(n1);
        for (ListNode p = h; p != null; p = p.next) {
            System.out.print(p.val + (p.next == null ? "
" : " -> "));
        }
        // Output: 18 -> 6 -> 6 -> 2 -> 10
    }
}

Complexity and Pitfalls

Time complexity : O(n) – one pass, each edge gets one inserted node, GCD computed via Euclidean algorithm.

Space complexity : O(1) extra space (excluding the newly created nodes).

Boundary cases : Empty list or single node returns unchanged; GCD with 0 yields |x|; negative numbers are converted to absolute values to avoid unexpected modulo results.

Robustness : If input guarantees positive integers, the absolute‑value step is harmless; for very long lists prefer an iterative GCD to avoid recursion stack overflow.

The key to solving this interview question is a careful in‑place insertion: back up next, insert the mid node, then advance to the original next node. Testing with a small example confirms correctness.