Skip to main content
Talentd

Insert Greatest Common Divisors in Linked List - Solution & Explanation

MediumLinked ListMathNumber Theory15 min readAsked at: Microsoft, Meta, Google +1
Practice this problem

Problem Statement

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:

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

Approach Overview

Problem 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.

Approach 1: Iterative Approach

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Recursive Approach

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Simulation

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), since we only use a fixed amount of additional space.

Recursive Approach

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.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Linked List TraversalO(n log V)O(1)Best general solution. Efficient pointer updates with constant extra space.
Recursive InsertionO(n log V)O(n)Useful for demonstrating recursion or cleaner conceptual implementation.

Video Solution

Insert Greatest Common Divisors in Linked List - Leetcode 2807 - Python • NeetCodeIO • 7,296 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Insert Greatest Common Divisors in Linked List easy or hard?
The problem is rated Medium. The main challenge is correctly manipulating linked list pointers while maintaining traversal order. Once the insertion logic is clear, the GCD calculation using the Euclidean algorithm is straightforward.
Insert Greatest Common Divisors in Linked List Python/Java solution
The Python and Java solutions both follow the same logic: iterate through the linked list, compute the GCD of adjacent node values, create a new node with that value, and insert it between the two nodes. The implementation runs in O(n log V) time and constant extra space.
How to solve Insert Greatest Common Divisors in Linked List in O(n)?
You traverse the linked list once and insert nodes on the fly. For each node and its next node, compute the GCD and create a new node between them by updating pointers. The traversal itself is O(n), while each GCD calculation contributes a small O(log V) factor.
What is the best approach for Insert Greatest Common Divisors in Linked List?
The best approach is iterative traversal of the linked list. For each adjacent pair of nodes, compute the GCD using the Euclidean algorithm and insert a new node between them. This processes each pair exactly once, giving O(n log V) time complexity and O(1) extra space.
Is Insert Greatest Common Divisors in Linked List asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving linked list pointer manipulation combined with basic math operations like GCD. Variations of linked list insertion and number theory operations frequently appear in interviews at companies such as Amazon, Google, and Meta.
What data structure is used in Insert Greatest Common Divisors in Linked List?
The primary data structure is a singly linked list. The algorithm performs pointer manipulation to insert new nodes between existing ones while using the Euclidean algorithm from number theory to compute the greatest common divisor.
What is the time complexity of Insert Greatest Common Divisors in Linked List?
The time complexity is O(n log V), where n is the number of nodes and V is the maximum node value. Each adjacent pair requires a GCD calculation, and the Euclidean algorithm runs in O(log V) time.

Ready to solve this problem?

Practice Insert Greatest Common Divisors in Linked List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Reverse Linked List