Insert greatest common divisors in linked list

Linked List Math Number Theory

91.4% acceptance

Feb 25, 2026

1137

Given the head of a linked list head, in which each node contains an integer value. Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them. Return the linked list after insertion. The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

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