Problem 2.3: Reverse (100 pts)

Define reverse, which takes in a linked list and reverses the order of the links. The function may not return a new list; it must mutate the original list. Return a pointer to the head of the reversed list.

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

There are at least three ways to solve this problem, can you come up with all?

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 ***"