URL

leetcode.com/problems/merge-k-sorted-lists

Code

github.com/syohex/dotnet-study/blob/master/..

type LinkedList<'a when 'a: comparison> =
    | ListEnd
    | ListNode of 'a * LinkedList<'a>

    static member toList(list: LinkedList<'a>) : ('a list) =
        let rec toList' list acc =
            match list with
            | ListEnd -> acc |> List.rev
            | ListNode (v, tail) -> toList' tail (v :: acc)

        toList' list []

let mergeKLists<'a when 'a: comparison> (lists: LinkedList<'a> list) : LinkedList<'a> =
    let rec mergeTwoLists l1 l2 =
        match (l1, l2) with
        | (ListEnd, ListEnd) -> ListEnd
        | (ListNode (n1, t1), ListEnd) -> ListNode(n1, (mergeTwoLists t1 ListEnd))
        | (ListEnd, ListNode (n2, t2)) -> ListNode(n2, (mergeTwoLists ListEnd t2))
        | (ListNode (n1, t1), ListNode (n2, t2)) ->
            if n1 < n2 then
                ListNode(n1, mergeTwoLists t1 l2)
            else
                ListNode(n2, mergeTwoLists l1 t2)

    match lists with
    | [] -> ListEnd
    | head :: tail -> tail |> List.fold mergeTwoLists head