2807.在链表中插入最大公约数

链接：2807.在链表中插入最大公约数
难度：Medium
标签：链表、数学、数论
简介：请你返回插入之后的链表。

题解 1 - python

• 编辑时间：2024-01-06
• 执行用时：72ms
• 内存消耗：19.92MB
• 编程语言：python
• 解法介绍：遍历。

def gcd(a: int, b: int) -> int:
        return gcd(b, a % b) if b != 0 else a
    class Solution:
        def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
            p = head
            while p.next:
                p.next = ListNode(gcd(p.val, p.next.val), p.next)
                p = p.next.next
            return head

题解 2 - rust

• 编辑时间：2024-01-06
• 执行用时：8ms
• 内存消耗：2.83MB
• 编程语言：rust
• 解法介绍：同上。

fn gcd(a: i32, b: i32) -> i32 {
    if a < b {
        gcd(b, a)
    } else if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}
impl Solution {
    pub fn insert_greatest_common_divisors(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut head = head.unwrap();
        let mut p = &mut head;
        while let Some(mut next) = p.next.take() {
            let mut new_next = Box::new(ListNode::new(gcd(p.val, next.val)));
            new_next.next = Some(next);
            p.next = Some(new_next);
            p = p.next.as_mut().unwrap().next.as_mut().unwrap();
        }
        Some(head)
    }
}