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 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:
[1, 5000].1 <= Node.val <= 1000In #2807 Insert Greatest Common Divisors in Linked List, the goal is to insert a new node between every pair of adjacent nodes where the value is the greatest common divisor (GCD) of the two nodes. Since the structure is a linked list, the most efficient approach is to traverse the list once while examining each pair of neighboring nodes.
For every current node, compute the GCD of its value and the next node’s value using the Euclidean algorithm. After calculating the GCD, create a new node with that value and insert it between the two nodes by adjusting pointers. Then continue traversal from the original next node to avoid reprocessing inserted nodes.
This method leverages simple pointer manipulation and efficient GCD computation. Because each original node is processed once, the traversal remains linear. The GCD calculation introduces a small logarithmic factor based on the node values.
Time Complexity: O(n log V) where n is the number of nodes and V is the maximum node value. Space Complexity: O(1) extra space since the operations are performed in-place.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass Linked List Traversal with GCD Insertion | O(n log V) | O(1) |
NeetCodeIO
This approach involves iterating through the linked list while moving two pointers: a 'current' pointer to track the current node, and a 'next_node' pointer to track the next node. For each pair of adjacent nodes, compute their GCD and insert a new node with this GCD value between them.
Time Complexity: O(n), where n is the number of nodes, as we traverse once through the list and perform constant-time operations on each pair of nodes.
Space Complexity: O(1), since we only use a fixed amount of additional space.
1#include <algorithm>
2using namespace std;
3
4struct ListNode {
5 int val;
6 ListNode* next;
7 ListNode(int x) : val(x), next(nullptr) {}
8};
9
10class Solution {
11public:
12 ListNode* insertGcds(ListNode* head) {
13 if (!head || !head->next) return head;
14
ListNode* current = head;
while (current && current->next) {
int gcdValue = gcd(current->val, current->next->val);
ListNode* newNode = new ListNode(gcdValue);
newNode->next = current->next;
current->next = newNode;
current = newNode->next;
}
return head;
}
};This C++ solution uses the standard library 'gcd' function. It traverses the list with a 'current' pointer, inserts each new node with the GCD value between two nodes, and updates pointers accordingly to maintain the list structure.
This recursive approach operates similarly to the iterative version but employs recursion to achieve insertion. It recursively inserts GCD nodes starting from the head of the linked list and processes each node until the end.
Time Complexity: O(n), where n is the size of the linked list.
Space Complexity: O(n) due to the stack space used in recursion.
1class ListNode:
2 def __init__(self,
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
The GCD is typically computed using the Euclidean algorithm, which repeatedly applies modulo operations until the remainder becomes zero. This method runs in logarithmic time relative to the values of the numbers, making it efficient for repeated calculations during traversal.
Yes, variations of linked list manipulation problems combined with mathematical operations are common in coding interviews. This problem tests understanding of pointer operations, traversal logic, and efficient number theory techniques like GCD.
The primary data structure used is a singly linked list. The solution focuses on pointer manipulation to insert new nodes while traversing the list and computing GCD values between adjacent nodes.
The optimal approach is to traverse the linked list once and compute the GCD for every pair of adjacent nodes. After calculating the GCD using the Euclidean algorithm, insert a new node containing that value between the two nodes. This maintains linear traversal with constant extra space.
The Python recursive solution inserts the GCD nodes between each pair of nodes in the linked list. The recursion base case is reached when there's either one node or no nodes left to process. By handling nodes recursively, the function continues until the entire list is processed.