題目敘述 Insert Greatest Common Divisors in Linked List
題目給定一個鏈結串列，
請在兩兩節點之間加入一個新節點，新節點的值為兩者之間的最大公因數。
測試範例
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~5000之間。
1 <= Node.val <= 1000
節點值都介於1~1000之間。
演算法 兩兩一組為單元操作。
兩兩一組為單元操作。
先計算相鄰兩節點之間的最大公因數GCD，
接著在中間插入新結點。
接著移動到下一個位置，如此反覆操作，直到串列尾端為止。
Python 程式碼 兩兩一組為單元操作
class Solution:
def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
## Base case
# Empty list or only one node
if not head or not head.next:
return head
## General cases
# Locate next node
next_hop = head.next
# Compute gcd between next node and current node
_gcd = math.gcd(head.val, next_hop.val)
# Insert node with GCD value
head.next = ListNode( _gcd, next_hop)
# Go to original next node
self.insertGreatestCommonDivisors(next_hop)
return head
Go 程式碼 兩兩一組為單元操作
func getGCD(a, b int) int{
// Euclid algorithm to find GCD
for b != 0{
a, b = b, a % b
}
return a
}
func insertGreatestCommonDivisors(head *ListNode) *ListNode {
// Base Case
if head == nil || head.Next == nil{
return head
}
// General case
// Locate original next node
nextHop := head.Next
// Compute GCD between current node and next node
_gcd := getGCD(head.Val, nextHop.Val)
// Insert node of GCD
head.Next = &ListNode{Val: _gcd, Next: nextHop}
// Going to original next node
insertGreatestCommonDivisors(nextHop)
return head
}
複雜度分析
時間複雜度: O(n)
從頭到尾拜訪每個節點，總共耗時為O(n)
空間複雜度: O(n)
從頭到尾拜訪每個節點，遞迴深度 = run time call stack深度 = O(n)
Reference
[1] Insert Greatest Common Divisors in Linked List - LeetCode
