Problem 2.2: Reverse (100 pts)

Write a function reverse which takes in a linked list lnk, reverses the order of it and returns the reversed list(i.e. return a new reference to the head of the reversed list). Your implementation should mutate the original linked list. DO NOT create any new linked lists.

You may not just simply exchange the first to reverse the list. On the contrary, you should make change on rest.

There is more than one way to solve this problem. Can you come up with more solutions?

def reverse(lnk):
    """ Reverse a linked list.

    >>> a = Link(1, Link(2, Link(3)))
    >>> # Disallow the use of making new Links before calling reverse
    >>> Link.__init__, hold = lambda *args: print("Do not steal chicken!"), Link.__init__
    >>> try:
    ...     r = reverse(a)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(r)
    <3 2 1>
    >>> a.first # Make sure you do not change first
    1
    """
    "*** YOUR CODE HERE ***"