🏅環環相扣 插入GCD到鏈結串列中_Insert GCD in Linked List_Leetcode #2807

Maxim Mox on Unsplash

題目敘述 Insert Greatest Common Divisors in Linked List

題目給定一個鏈結串列，
請在兩兩節點之間加入一個新節點，新節點的值為兩者之間的最大公因數。

最後返回新串列的head node作為答案。

測試範例

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