URL

https://leetcode.com/problems/linked-list-random-node/description/

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/problems/0382/main.fsx

open System

type LinkedList =
    | Leaf
    | Node of int * LinkedList

type Solution =
    { Head: LinkedList
      Rand: Random }

    static member init(list: LinkedList) : Solution = { Head = list; Rand = new Random() }

    member this.getRandom() : int =
        let rec getRandom' list (rand: Random) n acc =
            match list with
            | Leaf -> acc
            | Node(v, next) ->
                let r = rand.NextDouble()
                if r < 1.0 / n then
                    getRandom' next rand (n + 1.0) v
                else
                    getRandom' next rand (n + 1.0) acc

        getRandom' this.Head this.Rand 1.0 0