Insert Greatest Common Divisors in Linked List

Problem Description

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.

Examples

Constraints

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

Single Pass Iterative Traversal

Traverse the linked list with a single pointer curr. At each step:

1. Identify the next node next = curr.next.
2. If next is not null, calculate the GCD of curr.val and next.val.
3. Create a new node with this GCD value.
4. Insert it between curr and next by updating pointers: curr.next = gcdNode and gcdNode.next = next.
5. Move curr to next to process the next pair.

Solution

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode curr = head;
        while (curr.next != null) {
            ListNode next = curr.next;
            int gcdVal = gcd(curr.val, next.val);

            ListNode gcdNode = new ListNode(gcdVal);
            curr.next = gcdNode;
            gcdNode.next = next;

            curr = next; // skip the newly inserted node
        }
        return head;
    }

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

import math

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        curr = head
        while curr.next:
            next_node = curr.next
            gcd_val = math.gcd(curr.val, next_node.val)

            gcd_node = ListNode(gcd_val)
            curr.next = gcd_node
            gcd_node.next = next_node

            curr = next_node
            
        return head

#include <numeric>

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        if (!head || !head.next) return head;

        ListNode* curr = head;
        while (curr->next) {
            ListNode* nextNode = curr->next;
            int gcdVal = std::gcd(curr->val, nextNode->val);

            ListNode* gcdNode = new ListNode(gcdVal);
            curr->next = gcdNode;
            gcdNode->next = nextNode;

            curr = nextNode;
        }
        return head;
    }
};

Complexity Analysis:

• Time Complexity: O(N * log(min(A, B))) where N is the number of nodes in the linked list, and A, B are adjacent node values. Finding GCD of values up to 1000 is extremely fast (at most 10 iterations).
• Space Complexity: O(1) auxiliary space.

← All Problems