mutable struct ListNode
    data
    next::Union{Nothing, ListNode}
end

LinkedList = Union{Nothing, ListNode}

function car(lst::LinkedList)
    if lst == nothing
        error("empty list")
    else
        return lst.data
    end
end

function cdr(lst::LinkedList)
    if lst == nothing
        error("empty list")
    else
        return lst.next
    end
end

function len(lst::LinkedList)
    if lst == nothing
        return 0
    else
        return len(cdr(lst))+1
    end
end

function sum(lst::LinkedList)
    if lst == nothing
        return 0
    else
        return sum(lst.next) + lst.data
    end
end

function sum_tr(lst::LinkedList)
    return sum_tr(lst, 0)
end

function sum_tr(lst::LinkedList, acc::Int)
    if lst == nothing
        return acc
    else
        return sum_tr(lst.next, acc+lst.data)
    end
end

function sum2(lst::LinkedList)
    s = 0
    while lst != nothing
        s += lst.data
        lst = lst.next
    end
    return s
end

function vector_2_linkedlist(v::Vector{Int})
    lst = nothing
    for i in length(v):-1:1
        lst = ListNode(v[i], lst)
    end
    return lst
end

lst = vector_2_linkedlist(collect(1:1000000))

function min_max(lst::LinkedList)
    min = max = lst.data
    lst = lst.next
    while lst != nothing
        min = Base.min(min, lst.data)
        max = Base.max(max, lst.data)
        lst = lst.next
    end
    return (min, max)
end

function reverse(lst::LinkedList)
    rlst = nothing
    while lst != nothing
        rlst = ListNode(lst.data, rlst)
        lst = lst.next
    end
    return rlst
end

#@time println(sum(lst))

#@time println(sum_tr(lst))

@time println(sum2(lst))