Insert Greatest Common Divisors in Linked List

MEDIUM

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.

Example 1:

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1^st diagram denotes the initial linked list and the 2^nd 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 1^st and the 2^nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2^nd and the 3^rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3^rd and the 4^th nodes.
There are no more adjacent nodes, so we return the linked list.

Example 2:

Input: head = [7]
Output: [7]
Explanation: The 1^st diagram denotes the initial linked list and the 2^nd 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

Approaches

Checkout 2 different approaches to solve Insert Greatest Common Divisors in Linked List. Click on different approaches to view the approach and algorithm in detail.

In-place Modification

A more optimal approach in terms of space complexity is to modify the list in-place. We traverse the list, and for each adjacent pair of nodes, we create the new GCD node and insert it between them by rearranging the next pointers.

Algorithm

Initialize a pointer current = head.
If the list is empty or has only one node, no insertions are needed, so return head.
Iterate through the list with the condition while (current.next != null):
- a. Store the reference to the next node: nextNode = current.next.
- b. Calculate the GCD of current.val and nextNode.val.
- c. Create a new ListNode with the GCD value.
- d. Rewire the pointers to insert the new node: current.next = newNode and newNode.next = nextNode.
- e. Move current to the next node of the original list to process the next pair: current = nextNode.
Return the original head, which now points to the modified list.

We traverse the list with a pointer, let's call it current, starting at the head. The loop continues as long as current.next is not null, ensuring we can always form a pair (current, current.next). In each iteration, we first get a handle on the node after current, let's call it nextNode. Then, we compute the GCD of current.val and nextNode.val. A new node is created with this GCD value. This new node is inserted between current and nextNode by setting current.next to the new node, and the new node's next to nextNode. Finally, to proceed to the next pair of original nodes, we advance current to nextNode. The process repeats until the end of the list is reached.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode current = head;
        while (current.next != null) {
            ListNode nextNode = current.next;
            
            // Calculate GCD
            int gcdVal = gcd(current.val, nextNode.val);
            
            // Create and insert the new node
            ListNode newNode = new ListNode(gcdVal);
            newNode.next = nextNode;
            current.next = newNode;
            
            // Move to the next original node
            current = nextNode;
        }
        
        return head;
    }

    // Helper function to calculate GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Complexity Analysis

Time Complexity: O(N * log(K)), where N is the number of nodes in the original list and K is the maximum value in a node. We traverse the original list once, and each step involves a GCD calculation.Space Complexity: O(1). We modify the list in-place. The space for the new nodes is part of the output structure and is not considered extra auxiliary space. The only extra space is for a few pointers and variables, which is constant.

Pros and Cons

Pros:

Extremely space-efficient, using only O(1) auxiliary space.
Avoids the overhead of allocating an entire new list.

Cons:

Modifies the input list, which might be a side effect to avoid in some applications.

Code Solutions

Checking out 3 solutions in different languages for Insert Greatest Common Divisors in Linked List. Click on different languages to view the code.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode insertGreatestCommonDivisors ( ListNode head ) { for ( ListNode pre = head , cur = head . next ; cur != null ; cur = cur . next ) { int x = gcd ( pre . val , cur . val ); pre . next = new ListNode ( x , cur ); pre = cur ; } return head ; } private int gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ); } }

Video Solution

Watch the video walkthrough for Insert Greatest Common Divisors in Linked List

Patterns:

MathNumber Theory

Data Structures:

Linked List