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

描述 §

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

给你一个链表的头 head ，每个结点包含一个整数值。

在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。

请你返回插入之后的链表。

两个数的 最大公约数 是可以被两个数字整除的最大正整数。

思路 §

模拟执行

代码 §

impl Solution {  
    pub fn insert_greatest_common_divisors(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {  
        let mut cur = &mut head;  
  
        while cur.as_ref().unwrap().next.is_some() {  
            let x = cur.as_mut().unwrap();  
            let next = x.next.take();  
            x.next = Some(Box::new(ListNode {  
                val: Self::gcd(x.val, next.as_ref().unwrap().val),  
                next,  
            }));  
            cur = &mut cur.as_mut().unwrap().next.as_mut().unwrap().next;  
        }  
  
        head  
    }  
  
    fn gcd(mut a: i32, mut b: i32) -> i32 {  
        while a != 0 {  
            (a, b) = (b % a, a);  
        }  
        b  
    }  
}

分类 §

#算法/链表