Watch 10 video solutions for Insert Greatest Common Divisors in Linked List, a medium level problem involving Linked List, Math, Number Theory. This walkthrough by NeetCodeIO has 7,008 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |