Insert Greatest Common Divisors in Linked List
The key idea
Walk the list one adjacent pair at a time. For each pair
(a, b) compute gcd(a, b), build a node holding it, and splice that node between a and b. The greatest common divisor is found with the Euclidean algorithm: repeatedly replace the larger number by its remainder when divided by the smaller until one becomes 0.Problem
A linked list is given to you with head as its first node. Each node holds an integer in val. Between every pair of adjacent nodes, insert a new node whose value is the greatest common divisor of the two neighbours.
The greatest common divisor of two numbers is the largest positive integer that divides both of them exactly. After inserting all the new nodes, return the head of the modified linked list. The original nodes keep their order and their values; you only add the divisor nodes in between.
Constraints
- The number of nodes in the list is in the range
[1, 5000]. 1 <= Node.val <= 1000
Examples
Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Input: head = [8,12,18]
Output: [8,4,12,6,18]
Input: head = [7]
Output: [7]
Complexity
Time: O(n log M) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Linked List problems
- Add Two NumbersMEDIUM
- Copy List with Random PointerMEDIUM
- Design Linked ListMEDIUM
- Intersection of Two Linked ListsEASY
- Maximum Twin Sum of a Linked ListMEDIUM
- Merge Two Sorted ListsEASY
- Odd Even Linked ListMEDIUM
- Partition ListMEDIUM
- Remove Duplicates from Sorted List IIMEDIUM
- Remove Linked List ElementsEASY
- Remove Nth Node From End of ListMEDIUM
- Reorder ListMEDIUM