Insert Greatest Common Divisors in Linked List

Updated on 17 June, 2025
Insert Greatest Common Divisors in Linked List header image

Problem Statement

In this task, we are dealing with a linked list where each node contains an integer value. The challenge is to insert a new node between every pair of adjacent original nodes. The value of these new nodes should be the greatest common divisor (GCD) of the two adjacent nodes. The GCD is defined as the largest positive integer that divides both integers without leaving a remainder. Our goal is to return the modified linked list after inserting these GCD nodes.

Examples

Example 1

Input:

head = [18,6,10,3]

Output:

[18,6,6,2,10,1,3]

Explanation:

The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.

Example 2

Input:

head = [7]

Output:

[7]

Explanation:

The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.

Constraints

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

Approach and Intuition

  1. To tackle this problem, we first need to traverse the linked list from the beginning to the end.
  2. As we traverse through each pair of adjacent nodes, we calculate their GCD.
  3. This GCD calculation can be efficiently done using the Euclidean algorithm, where the GCD of two numbers is obtained by repeatedly replacing the larger number by its remainder when divided by the smaller number until one of the numbers becomes zero. The non-zero number then is the GCD of the original two numbers.
  4. We then create a new node with this GCD value and insert it between the two current nodes.
  5. Continue this process until there are no more pairs of adjacent nodes.
  6. If the list starts with only one or no nodes, no insertion is necessary, and the original list is returned as is.

Let's consider the examples to understand this approach better:

  • In the provided example setting head = [18,6,10,3], the GCD of the first pair (18 and 6) is 6, which gets inserted between them. Following this method, the GCDs of subsequent pairs (6 & 10, and 10 & 3) are calculated as 2 and 1 respectively and are inserted accordingly. Thus, the list transforms with the addition of these new GCD nodes.

  • For a single element list like head = [7], since there are no adjacent nodes, no operation is performed, and the original list remains the same.

This illustrates that our approach will manage effectively regardless of the list's length, adhering to the insertion requirement and returning the correctly modified linked list.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    ListNode* insertGCDs(ListNode* root) {
        // Return root if only one node is present
        if (!root->next) return root;
    
        // Pointers to navigate through the list
        ListNode* currentNode = root;
        ListNode* nextNode = root->next;
    
        // Process each node pair in the linked list
        while (nextNode != nullptr) {
            int gcd = computeGCD(currentNode->val, nextNode->val);
            ListNode* gcdNode = new ListNode(gcd);
    
            // Insert the GCD node between current and next node
            currentNode->next = gcdNode;
            gcdNode->next = nextNode;
    
            // Update pointers to move to the next nodes in the list
            currentNode = nextNode;
            nextNode = nextNode->next;
        }
    
        return root;
    }
    
private:
    // Compute GCD using Euclidean algorithm
    int computeGCD(int x, int y) {
        while (y != 0) {
            int remainder = y;
            y = x % y;
            x = remainder;
        }
        return x;
    }
};

This solution presents a method to modify a linked list by inserting nodes containing the Greatest Common Divisor (GCD) of consecutive values. The code is written in C++ and defines a class Solution with the method insertGCDs to perform the operation on the linked list.

Steps involved in the code:

  1. Check if the linked list has only one node. In this case, return the root as no insertion is required.
  2. Initialize two pointers, currentNode and nextNode, to traverse the linked list starting from the root.
  3. For each pair of consecutive nodes, compute the GCD of their values using the nested function computeGCD, which implements the Euclidean algorithm.
  4. Create a new node (gcdNode) with the computed GCD value and insert it between the current node and the next node.
  5. Adjust the next pointers to ensure currentNode now points to gcdNode and gcdNode points to nextNode.
  6. Continue the process by moving currentNode and nextNode forward in the list.
  7. Once all GCD nodes are inserted, return the modified root of the list.

The computeGCD private member function iteratively applies the Euclidean algorithm to find the GCD, ensuring the nodes inserted contain accurate GCD values. Through the use of pointers and dynamic node creation, the linked list is effectively modified in-place.

java
class Solution {
    
    public ListNode addGCDNodes(ListNode head) {
        if (head.next == null) return head;
    
        ListNode current = head;
        ListNode nextNode = head.next;
    
        while (nextNode != null) {
            int gcd = findGCD(current.val, nextNode.val);
            ListNode newGCDNode = new ListNode(gcd);
    
            current.next = newGCDNode;
            newGCDNode.next = nextNode;
    
            current = nextNode;
            nextNode = nextNode.next;
        }
    
        return head;
    }
    
    private int findGCD(int x, int y) {
        while (y != 0) {
            int t = y;
            y = x % y;
            x = t;
        }
        return x;
    }
}

The Java code you provided defines a method to insert nodes into a linked list, where each new node's value is the greatest common divisor (GCD) of the values of adjacent nodes. Here's a breakdown of how this function operates:

  • The method addGCDNodes begins by checking if the list contains only one node. If it does, the list is returned unchanged.

  • A while loop iterates through the nodes of the list. During each iteration, it calculates the GCD of the values of two consecutive nodes (current and nextNode). This is accomplished through the helper method findGCD.

  • A new node, storing the computed GCD, is created and inserted between current and nextNode.

  • The list traversal continues until all appropriate GCD nodes have been added.

The findGCD function employs Euclid's algorithm to compute the GCD of two integers. It repeatedly replaces the larger number with the remainder of the two numbers until one of the numbers becomes zero, at which point the other number is the GCD.

When utilizing this code in your linked list operations, you ensure that every pair of adjacent nodes contributes a new node containing their GCD, enriching the data structure with meaningful mathematical relationships between its elements. This method efficiently processes linked list nodes and inserts new nodes as required, all while maintaining the linked list's structural integrity.

python
class Solution:
    def insertGCDNodes(
        self, head: Optional[ListNode]
    ) -> Optional[ListNode]:
        # Method to find GCD using the Euclidean algorithm
        def compute_gcd(x, y):
            while y != 0:
                x, y = y, x % y
            return x
    
        # Return early if the list has only one node
        if not head.next:
            return head
    
        # Starting pointers for the list iteration
        current = head
        next_node = head.next
    
        # Iterate through the linked list and insert GCD nodes
        while next_node:
            gcd = compute_gcd(current.val, next_node.val)
            gcd_new_node = ListNode(gcd)
    
            # Link the new GCD node between current and next_node
            current.next = gcd_new_node
            gcd_new_node.next = next_node
    
            # Update pointers to next relevant nodes
            current = next_node
            next_node = next_node.next
    
        return head

This Python solution is designed to manage a linked list by inserting nodes that represent the Greatest Common Divisor (GCD) of consecutive nodes. The solution employs the Euclidean algorithm to compute the GCD. Here is an overview of the process:

  1. Define a helper function compute_gcd(x, y) to calculate the GCD using the Euclidean algorithm.
  2. Check if the linked list has only one node and return the head if it does.
  3. Initialize pointers, current and next_node, to traverse the linked list starting from the head.
  4. Iterate through the linked list. For each pair of consecutive nodes:
    • Compute the GCD of their values.
    • Create a new node with the GCD value.
    • Insert the new GCD node between the current and the next node.
    • Update the current pointer to the node right after the newly inserted GCD node.
    • Continue this process until the end of the linked list.
  5. Return the modified linked list head with the new GCD nodes inserted.

This method ensures the linked list is augmented efficiently with the GCD values in place, maintaining the original list structure while integrating valuable computational nodes.

Comments

No comments yet.