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 <= 1000This 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.
Java
C++
C
C#
JavaScript
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.
Java
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.
| 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. |
Insert Greatest Common Divisors in Linked List - Leetcode 2807 - Python • NeetCodeIO • 5,812 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