Solutions: You can find the file with solutions for all questions here.

A linked list is either an empty linked list (`Link.empty`) or a first value and the rest of the linked list.

``````class Link:
"""
>>> s
"""
empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest

def __repr__(self):
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''

To check if a `Link` is empty, compare it against the class attribute `Link.empty`. For example, the below function prints out whether or not the link it is handed is empty:

``````def test_empty(link):
else:
print('This linked list is not empty!')``````

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (`first`) and a reference to another linked list (`rest`) which contains the rest of the values in the list.

Write a function `link_to_list` that converts a given `Link` to a Python list.

``````def link_to_list(link):
"""Takes a Link and returns a Python list with the same elements.

[1, 2, 3, 4]
[88]
[]
"""
# Recursive solution
return []

# Iterative solution
result = []
return result``````

Use OK to test your code:

``python3 ok -q link_to_list``

Question 2: Every Other

Implement `every_other`, which takes a linked list `s`. It mutates `s` such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

``````>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
True``````

If `s` contains fewer than two elements, `s` remains unchanged.

Do not return anything! `every_other` should mutate the original list.

``````def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).

>>> every_other(s)
>>> s
>>> every_other(odd_length)
>>> odd_length
>>> every_other(singleton)
>>> singleton
"""
return
else:
s.rest = s.rest.rest
every_other(s.rest)``````

Use OK to test your code:

``python3 ok -q every_other``

Question 3: Slice

Implement a function `slice_link` that slices a given `link`. `slice_link` should slice the `link` starting at `start` and ending one element before `end`, as with a normal Python list.

``````def slice_link(link, start, end):
"""Slices a Link from start to end (as with a normal Python list).

<1 4 1>
<1>
<>
"""
if end == 0:
elif start == 0:
else:

Use OK to test your code:

``python3 ok -q slice_link``

Question 4: Deep Map

Implement `deep_map`, which takes a function `f` and a `link`. It returns a new linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`.

The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself.

Hint: You may find the built-in `isinstance` function useful.

``````def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.

>>> print_link(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
<1 <2 3> 4>
<<2 <4 6> 8> <<10>>>
"""
``python3 ok -q deep_map``
``python3 ok --submit``