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 <= 1000Problem Overview: You are given the head of a singly linked list. For every pair of adjacent nodes, compute their greatest common divisor (GCD) and insert a new node containing that value between them. The final list alternates between original nodes and newly inserted GCD nodes.
Approach 1: Iterative Linked List Traversal (O(n log V) time, O(1) space)
Walk through the linked list one pair at a time. For each node curr and its next node curr.next, compute the GCD using the Euclidean algorithm from number theory. Create a new node with this value and insert it between the two nodes by adjusting pointers: curr.next = gcdNode and gcdNode.next = nextNode. Then move the pointer two steps forward to continue with the next original pair.
The key insight is that insertion does not require rebuilding the list. You reuse the existing structure and only adjust pointers locally. The Euclidean GCD computation runs in O(log V) where V is the node value, so processing n nodes results in O(n log V) time overall while maintaining constant auxiliary space.
This approach is optimal because each edge between adjacent nodes is processed exactly once. It is also simple to implement and works directly on the list without extra data structures.
Approach 2: Recursive Insertion (O(n log V) time, O(n) space)
The recursive version processes the list pair-by-pair using the call stack. For the current node, compute the GCD with its next node using the Euclidean algorithm from math. Insert a new node between them, then recursively process the remainder of the list starting from the original next node.
This produces the same final structure as the iterative solution. However, recursion introduces O(n) stack usage because each pair generates a recursive call. While elegant, it is less memory efficient and may hit recursion limits for very large lists.
Recommended for interviews: The iterative traversal is the expected solution. It demonstrates solid understanding of pointer manipulation in linked lists and efficient GCD computation. Mentioning the recursive variant shows deeper understanding, but interviewers typically prefer the iterative implementation due to constant space usage.
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.
The Python code defines a ListNode class and uses Python's inbuilt 'gcd' function from the math module. It traverses the linked list with a pointer called 'current'. For each pair of adjacent nodes, it calculates the GCD and inserts a new node containing this GCD between the nodes. The function handles empty or single-node lists as a base case.
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.
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.
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.
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.
We use two pointers pre and cur to point to the current node and the next node respectively. We only need to insert a new node between pre and cur. Therefore, each time we calculate the greatest common divisor x of pre and cur, we insert a new node with value x between pre and cur. Then we update pre = cur and cur = cur.next, and continue to traverse the linked list until cur is null.
The time complexity is O(n times log M), where n is the length of the linked list, and M is the maximum value of the nodes in the linked list. Ignoring the space consumption of the result linked list, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Approach | 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. |
| Recursive Approach | Time Complexity: O(n), where n is the size of the linked list. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Linked List Traversal | O(n log V) | O(1) | Best general solution. Efficient pointer updates with constant extra space. |
| Recursive Insertion | O(n log V) | O(n) | Useful for demonstrating recursion or cleaner conceptual implementation. |
Insert Greatest Common Divisors in Linked List - Leetcode 2807 - Python • NeetCodeIO • 7,008 views views
Watch 9 more video solutions →Practice Insert Greatest Common Divisors in Linked List with our built-in code editor and test cases.
Practice on FleetCode