URL

Insert Greatest Common Divisors in Linked List - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202409/insert_greatest_common_divisors_in_linked_list/main.fsx

type MyList =
    | Nil
    | Node of int * MyList

let gcd (a: int) (b: int) : int =
    let rec gcd' a b =
        let m = a % b
        if m = 0 then b else gcd' b m

    gcd' (max a b) (min a b)

let rec insertGreatestCommonDivisors (head: MyList) : MyList =
    match head with
    | Nil -> Nil
    | Node(v1, next) ->
        match next with
        | Nil -> head
        | Node(v2, _) ->
            let d = gcd v1 v2
            Node(v1, Node(d, insertGreatestCommonDivisors next))