2807. Insert Greatest Common Divisors in Linked List Medium

1/**
2 * [2807] Insert Greatest Common Divisors in Linked List
3 *
4 * Given the head of a linked list head, in which each node contains an integer value.
5 * Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.
6 * Return the linked list after insertion.
7 * The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
8 *  
9 * <strong class="example">Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2023/07/18/ex1_copy.png" style="width: 641px; height: 181px;" />
11 * Input: head = [18,6,10,3]
12 * Output: [18,6,6,2,10,1,3]
13 * Explanation: The 1^st diagram denotes the initial linked list and the 2^nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
14 * - We insert the greatest common divisor of 18 and 6 = 6 between the 1^st and the 2^nd nodes.
15 * - We insert the greatest common divisor of 6 and 10 = 2 between the 2^nd and the 3^rd nodes.
16 * - We insert the greatest common divisor of 10 and 3 = 1 between the 3^rd and the 4^th nodes.
17 * There are no more adjacent nodes, so we return the linked list.
18 * 
19 * <strong class="example">Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2023/07/18/ex2_copy1.png" style="width: 51px; height: 191px;" />
21 * Input: head = [7]
22 * Output: [7]
23 * Explanation: The 1^st diagram denotes the initial linked list and the 2^nd diagram denotes the linked list after inserting the new nodes.
24 * There are no pairs of adjacent nodes, so we return the initial linked list.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	The number of nodes in the list is in the range [1, 5000].
30 * 	1 <= Node.val <= 1000
31 * 
32 */
33pub struct Solution {}
34use crate::util::linked_list::{ListNode, to_list};
35
36// problem: https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/
37// discuss: https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41// Definition for singly-linked list.
42// #[derive(PartialEq, Eq, Clone, Debug)]
43// pub struct ListNode {
44//   pub val: i32,
45//   pub next: Option<Box<ListNode>>
46// }
47// 
48// impl ListNode {
49//   #[inline]
50//   fn new(val: i32) -> Self {
51//     ListNode {
52//       next: None,
53//       val
54//     }
55//   }
56// }
57impl Solution {
58    pub fn insert_greatest_common_divisors(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
59        Some(Box::new(ListNode::new(0)))
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_2807() {
71    }
72}
73