Insert Greatest Common Divisors in Linked List

Insert Greatest Common Divisors in Linked List - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: head = [18,6,10,3]

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

💡 Note: GCD(18,6)=6, insert 6. GCD(6,10)=2, insert 2. GCD(10,3)=1, insert 1. Result: [18,6,6,2,10,1,3]

Example 2 — Two Nodes

$ Input: head = [7]

› Output: [7]

💡 Note: Single node, no adjacent pairs exist, so no insertions needed

Example 3 — Coprime Numbers

$ Input: head = [7,11,13]

› Output: [7,1,11,1,13]

💡 Note: GCD(7,11)=1, GCD(11,13)=1. Prime numbers are coprime, so GCD is always 1

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list: 18 → 6 → 10 → 3

Process

Calculate GCD for each adjacent pair and insert

Output

Result: 18 → 6 → 6 → 2 → 10 → 1 → 3

Key Takeaway

🎯 Key Insight: Traverse once and use Euclidean algorithm for efficient GCD calculation while inserting nodes

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to traverse the linked list once and insert GCD nodes between adjacent pairs. Best approach uses the Euclidean algorithm for efficient GCD calculation. Time: O(n × log(min(a,b))), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Euclidean Algorithm	O(n × log(min(a,b)))	O(1)	Use efficient Euclidean algorithm to calculate GCD in O(log min(a,b)) time
Brute Force GCD	O(n × min(a,b))	O(1)	Calculate GCD by checking all divisors from 1 to min(a,b)

Euclidean Algorithm — Algorithm Steps

Traverse linked list node by node
For each adjacent pair, calculate GCD using Euclidean algorithm
Create new node with GCD value and insert between them

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Values

Start with a=18, b=6

Apply GCD(a,b) = GCD(b, a%b)

GCD(18,6) = GCD(6, 18%6) = GCD(6,0)

Insert GCD Node

When b=0, GCD is 6, insert new node

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    
    struct ListNode* current = head;
    while (current && current->next) {
        int gcdVal = gcd(current->val, current->next->val);
        struct ListNode* newNode = malloc(sizeof(struct ListNode));
        newNode->val = gcdVal;
        newNode->next = current->next;
        current->next = newNode;
        current = newNode->next;
    }
    
    return head;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int arr[1000], size = 0;
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            arr[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    
    printf("[");
    struct ListNode* current = result;
    int first = 1;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(min(a,b)))

Visit n nodes, Euclidean algorithm takes O(log min(a,b)) time for each GCD

⚡ Linearithmic

Space Complexity

O(1)

Only use a few variables, modify list in place

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Euclidean Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler