【Leetcode Daily】2807在链表中插入最大公约数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个链表，现在在每两个节点空隙插入一个节点，值为左右节点值的最大公约数，求最终的链表。

思路分享

• 最大公约数的求解直接用辗转相除法，Python 的 math 库中有现成的 gcd 函数调用。至于节点的插入，用两个指针，左指针指新节点，新节点指向右指针。

  https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list/solutions/2592797/jian-ji-xie-fa-pythonjavacgojsrust-by-en-i1rn/

代码解答（强烈建议自行解答后再看）

• 参考题解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def rcd(i:int, j:int):
    while i % j != 0:
        i, j = j, i % j
    return j
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # if not head.next:
        #     return head

        left, right = head, head
        while left.next:
            right = left.next
            new_node = ListNode(rcd(left.val, right.val), right)
            left.next = new_node
            left = right
        return head