Write out a function that will sum up all of the values in a linked list (the linked list may be nested). Assume there is at least one value in the list.
def sum_vals(lnk):
>>> lnk = Link(1, Link(2, Link(3, Link(4))))
>>> sum_vals(lnk)
10
    if lst.rest is Link.empty:
        return lst.first
    return lst.first + sum_vals(lst.rest)

Write out a function that will return true if y is a value in linked list lnk.
def search(lnk, y):
>>> lnk = Link(1, Link(2, Link(3, Link(4))))
>>> search(lnk, 4)
True
>>> search(lnk, 7)
False
    if lnk is Link.empty:
        return False
    return y == lnk.first or search(lnk.rest, y)

Write out a function that will take in a linked list and remove any links with odd first values from it (by creating a new linked list, not mutating lnk).
def remove_odd_nondestructive(lnk):
>>> lnk = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> remove_odd_nondestructive(lnk)
Link(2, Link(4))
>>> lnk
Link(1, Link(2, Link(3, Link(4, Link(5)))))
    if lnk is Link.empty:
        return lnk
    else if lnk.first % 2 != 0:
        return remove_odd_nondestructive(lnk.rest)
    return Link(lnk.first,remove_odd_nondestructive(lnk.rest))