🎨Now live: Try our Free AI Image Generation Feature

Description
Given a singly linked list, you are required to insert a node with the greatest common divisor (GCD) of two consecutive node values between every two adjacent nodes. This will modify the list in such a way that for each pair of consecutive nodes, a new node is inserted with the value of the GCD of their values.
Intuition
To solve this problem, we can calculate the GCD of two consecutive nodes in the linked list and insert a new node with this GCD value in between them. We iterate through the list and apply this process until we reach the end of the list.
The GCD of two numbers is the largest number that divides both numbers without leaving a remainder. We can compute the GCD either through iterative or recursive approaches.
Approach
- Helper Function for GCD: We create a helper function to compute the GCD of two numbers. This can be done by iterating through all numbers from 2 to the smaller of the two numbers and checking which is the largest divisor common to both.
- Iterating Through the List: We traverse the linked list starting from the head. For each pair of consecutive nodes, we compute their GCD and insert a new node with this value between the two nodes.
- Insertion: After computing the GCD for a pair of nodes, we create a new node with the GCD value and adjust the
next
pointers to insert the node between the current node and the next node. - Repeat: We continue this process until the end of the list, modifying the list in place by adding new nodes.
Complexity
Time Complexity:
- Calculating the GCD between two numbers takes O(min(a, b)) where
a
andb
are the two numbers. - For a linked list of
n
nodes, we perform this operationn - 1
times (once between each consecutive pair of nodes). Therefore, the time complexity is O(n * min(a, b)), wheren
is the number of nodes in the list.
Space Complexity:
- The space complexity is O(1) if we ignore the space used by the new nodes. The algorithm works in-place, but additional nodes are created, which leads to a space usage proportional to the size of the new nodes added.
- Including the new nodes, the space complexity would be O(n) where
n
is the number of original nodes, as each insertion creates an additional node.
Code
C++
class Solution {
public:
int findGCD(int num1, int num2) {
int smaller = std::min(num1, num2);
int maxGCD = 1;
for (int i = 2; i <= smaller; i++) {
if (num1 % i == 0 && num2 % i == 0) {
maxGCD = i;
}
}
return maxGCD;
}
ListNode* insertGreatestCommonDivisors(ListNode* head) {
ListNode* curr = head;
while (curr->next != nullptr) {
ListNode* next = curr->next;
int gcd = findGCD(curr->val, next->val);
curr->next = new ListNode(gcd, next);
curr = curr->next->next;
}
return head;
}
};
Python
class Solution:
def findGCD(self, num1, num2):
smaller = min(num1, num2)
max_gcd = 1
for i in range(2, smaller + 1):
if num1 % i == 0 and num2 % i == 0:
max_gcd = i
return max_gcd
def insertGreatestCommonDivisors(self, head):
curr = head
while curr.next:
next_node = curr.next
gcd = self.findGCD(curr.val, next_node.val)
curr.next = ListNode(gcd, next_node)
curr = curr.next.next
return head
Java
/**
* 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 {
private int findGCD(int num1, int num2) {
int smaller = Math.min(num1, num2);
int maxGCD = 1;
for (int i = 2; i <= smaller; i++) {
if (num1 % i == 0 && num2 % i == 0) {
maxGCD = i;
}
}
return maxGCD;
}
public ListNode insertGreatestCommonDivisors(ListNode head) {
ListNode curr = head;
while (curr.next != null) {
ListNode next = curr.next;
int gcd = findGCD(curr.val, next.val);
curr.next = new ListNode(gcd, next);
curr = curr.next.next;
}
return head;
}
}
JavaScript
var insertGreatestCommonDivisors = function (head) {
let findGCD = function (num1, num2) {
let smaller = Math.min(num1, num2)
let max = 1
for (let i = 2; i <= smaller; i++) {
if (num1 % i === 0 && num2 % i === 0) {
max = i
}
}
return max
}
let curr = head
while (curr.next) {
let next = curr.next
let gcd = findGCD(curr.val, next.val)
curr.next = new ListNode(gcd, next)
curr = curr.next.next
}
return head
}