Insert Greatest Common Divisors in Linked List

How it works

The problem asks us to insert a new node between every pair of adjacent nodes, where the new node's value is the GCD of its neighbors. We traverse the list and for each pair of consecutive nodes, compute their gcd and create a new node with that value. The Euclidean algorithm efficiently computes the gcd: repeatedly replace the larger number with the remainder of dividing the two numbers until one becomes zero. The other number is the gcd. Since we're inserting nodes as we traverse, we need to be careful to advance the pointer past the newly inserted node to avoid processing it again.

Steps

1. Start with cur pointing to the head of the list.
2. While cur.next exists:
   • Get the values of cur and cur.next as n1 and n2.
   • Compute their gcd using the Euclidean algorithm.
   • Create a new node with the gcd value.
   • Insert it between cur and cur.next by adjusting pointers.
   • Move cur to cur.next.next to skip over the newly inserted node.
3. Return the head of the modified list.

Complexity

• Time complexity: O(n * log (min(a, b)))
• Space complexity:
  • O(n) space for the gcd ListNodes.
  • O(1) extra space.

Where n is the length of the given list, and a and b are two numbers passed to the gcd() function.

Things to watch for

Processing Newly Inserted Nodes

After inserting a GCD node between cur and cur.next, forgetting to skip over the newly inserted node causes an infinite loop. The pointer must advance by two positions (cur = cur.next.next) to move past both the inserted node and reach the next original node that needs processing.

Incorrect GCD Implementation

Implementing the Euclidean algorithm incorrectly by not handling the base case properly or swapping values in the wrong order. The algorithm should continue until one value becomes zero, and the order of operands in the modulo operation matters. Using a % b when a < b returns a, which is correct, but some implementations incorrectly assume a > b.

Off-by-One at List End

Attempting to access cur.next.val when cur.next is null causes a null pointer exception. The loop condition must be while cur.next (not while cur) to ensure there is always a valid pair of adjacent nodes to compute the GCD between.

from typing import Optional
from math import gcd

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd(a, b):
            while b > 0:
                a, b = b, a % b
            return a

        cur = head
        while cur.next:
            n1, n2 = cur.val, cur.next.val
            cur.next = ListNode(gcd(n1, n2), cur.next)
            cur = cur.next.next

        return head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        if (!head) return nullptr;

        ListNode* cur = head;

        while (cur->next) {
            int n1 = cur->val, n2 = cur->next->val;
            int gcdValue = gcd(n1, n2);
            ListNode* newNode = new ListNode(gcdValue, cur->next);
            cur->next = newNode;
            cur = newNode->next;
        }

        return head;
    }

private:
    int gcd(int a, int b) {
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};