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

### Question 1: List to Link

Write a function `list_to_link` that converts a Python list to a `Link`.

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

<1 2 3>
"""
if not lst:
else:

Use OK to test your code:

``python3 ok -q list_to_link``

### Question 2: Mutable Mapping

Implement `deep_map_mut(fn, link)`, which applies a function `fn` onto all elements in the given linked list `link`. If an element is itself a linked list, apply `fn` to each of its elements, and so on.

Hint: The built-in `isinstance` function may be useful.

``````>>> s = Link(1, Link(2, Link(3, Link(4))))
True
>>> isinstance(s, int)
False``````
``````def deep_map_mut(fn, link):
"""Mutates a deep link by replacing each item found with the
result of calling fn on the item.  Does NOT create new Links (so

Does not return the modified Link object.

>>> deep_map_mut(lambda x: x * x, link1)
<9 <16> 25 36>
"""
return
else:

Use OK to test your code:

``python3 ok -q deep_map_mut``

### Question 3: Reverse

Implement `reverse`, which takes a linked list `link` and returns a linked list containing the elements of `link` in reverse order. The original `link` should be unchanged.

``````def reverse(link):
"""Returns a Link that is the reverse of the original.

<1>
<3 2 1>
<1 2 3>
"""
return new

# Recursive solution
return t
else:

Use OK to test your code:

``python3 ok -q reverse``

### Question 4: Mutate Reverse

Implement `mutate_reverse`, which takes a linked list instance and mutates it so that its values appear in reverse order. For an extra challenge, find an implementation that requires only linear time in the length of the list (big-Theta n).

``````def mutate_reverse(link):
"""Mutates the Link so that its elements are reversed.

"""
return

# O(n) solution
"""Mutates the Link so that its elements are reversed.

"""

return result``````

Use OK to test your code:

``python3 ok -q mutate_reverse``

### Question 5: Insert

Implement a function `insert` that takes a `Link`, a `value`, and an `index`, and inserts the `value` into the `Link` at the given `index`. You can assume the linked list already has at least one element. Do not return anything — `insert` should mutate the linked list.

Note: If the index is out of bounds, you can raise an `IndexError` with:

``raise IndexError``
``````def insert(link, value, index):
"""Insert a value into a Link at the given index.

<1 2 3>
<9001 1 2 3>
<9001 1 100 2 3>
IndexError
"""
if index == 0:
raise IndexError
else:

# iterative solution
index -= 1
if index == 0:
else:
raise IndexError``````

Use OK to test your code:

``python3 ok -q insert``

### Question 6: 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>
"""
if end == 0:
elif start == 0:
else:

Use OK to test your code:

``python3 ok -q slice_link``

## Optional Questions

### Question 7: Rotate

Implement `rotate`, which takes a linked list `link` and a number `n`, and returns a linked list containing the elements of `link` shifted to the right `n` times.

``````def rotate(link, n):
"""Rotates the Link so that its elements are shifted to the right n times.

"""
length = 0
while ptr:
ptr = ptr.rest
length += 1
n %= length
``python3 ok -q rotate``