#2807
Insert Greatest Common Divisors in Linked List
pupil · 355 · lc medium +23 · verified · 91.4% accepted · 1,137 likes · top 100%
Description
The head of a linked list is given, where each node holds an integer.
Between every adjacent pair of nodes, insert a new node whose value equals the greatest common divisor of the two neighbors.
Return the modified linked list.
The greatest common divisor of two numbers is the largest positive integer that divides both evenly.
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.
Code
1
2
3
4
5
6
7
8