Insert Greatest Common Divisors in Linked List

Brute Force — Collect Values, Compute GCDs, Rebuild — Watch how we first collect all node values into an array, then rebuild the linked list with GCD nodes inserted between each original pair.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        // Step 1: Collect all values into an array
        vector<int> arr;
        ListNode* curr = head;
        while (curr) {
            arr.push_back(curr->val);
            curr = curr->next;
        }
        
        // Edge case: single node
        if (arr.size() <= 1) return head;
        
        // Step 2: Build new list with GCD nodes
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        for (int i = 0; i < (int)arr.size() - 1; i++) {
            tail->next = new ListNode(arr[i]);
            tail = tail->next;
            
            int gcdVal = __gcd(arr[i], arr[i + 1]);
            tail->next = new ListNode(gcdVal);
            tail = tail->next;
        }
        
        // Append last original node
        tail->next = new ListNode(arr.back());
        
        return dummy.next;
    }
};

from math import gcd
from typing import Optional

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Step 1: Collect all values into an array
        arr = []
        curr = head
        while curr:
            arr.append(curr.val)
            curr = curr.next
        
        # Edge case: single node
        if len(arr) <= 1:
            return head
        
        # Step 2: Build new list with GCD nodes
        dummy = ListNode(0)
        tail = dummy
        
        for i in range(len(arr) - 1):
            tail.next = ListNode(arr[i])
            tail = tail.next
            
            gcd_val = gcd(arr[i], arr[i + 1])
            tail.next = ListNode(gcd_val)
            tail = tail.next
        
        # Append last original node
        tail.next = ListNode(arr[-1])
        
        return dummy.next

import java.util.ArrayList;
import java.util.List;

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        // Step 1: Collect all values into an array
        List<Integer> arr = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            arr.add(curr.val);
            curr = curr.next;
        }
        
        // Edge case: single node
        if (arr.size() <= 1) return head;
        
        // Step 2: Build new list with GCD nodes
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        for (int i = 0; i < arr.size() - 1; i++) {
            tail.next = new ListNode(arr.get(i));
            tail = tail.next;
            
            int gcdVal = gcd(arr.get(i), arr.get(i + 1));
            tail.next = new ListNode(gcdVal);
            tail = tail.next;
        }
        
        // Append last original node
        tail.next = new ListNode(arr.get(arr.size() - 1));
        
        return dummy.next;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

In-Place Two-Pointer Insertion of GCD Nodes — Watch how two pointers traverse the original list, inserting GCD nodes between each adjacent pair without any auxiliary data structure.

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        // Edge case: empty list or single node
        if (!head || !head->next) return head;
        
        ListNode* prev = head;
        ListNode* curr = head->next;
        
        while (curr) {
            // Compute GCD of adjacent pair
            int gcdVal = __gcd(prev->val, curr->val);
            
            // Create new node and insert between prev and curr
            ListNode* newNode = new ListNode(gcdVal, curr);
            prev->next = newNode;
            
            // Advance pointers (skip over newly inserted node)
            prev = curr;
            curr = curr->next;
        }
        
        return head;
    }
};

from math import gcd
from typing import Optional

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Edge case: empty list or single node
        if not head or not head.next:
            return head
        
        prev = head
        curr = head.next
        
        while curr:
            # Compute GCD of adjacent pair
            gcd_val = gcd(prev.val, curr.val)
            
            # Create new node and insert between prev and curr
            new_node = ListNode(gcd_val, curr)
            prev.next = new_node
            
            # Advance pointers (skip over newly inserted node)
            prev = curr
            curr = curr.next
        
        return head

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        // Edge case: empty list or single node
        if (head == null || head.next == null) return head;
        
        ListNode prev = head;
        ListNode curr = head.next;
        
        while (curr != null) {
            // Compute GCD of adjacent pair
            int gcdVal = gcd(prev.val, curr.val);
            
            // Create new node and insert between prev and curr
            ListNode newNode = new ListNode(gcdVal, curr);
            prev.next = newNode;
            
            // Advance pointers (skip over newly inserted node)
            prev = curr;
            curr = curr.next;
        }
        
        return head;
    }
    
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}