Skip to content

Problem 2.2: Reverse (100 pts)

Problem

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).

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

编写一个函数 reverse，它接受一个链表 lnk，反转其顺序并返回反转后的链表（即返回指向反转后链表头部的引用）。

解决这个问题的方法不止一种。你能想出更多的解决方案吗？

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

Hints

Hint1: Your implementation should mutate the original linked list. DO NOT create any new linked lists.

Hint2: By reverse we mean the rest attribute of each Link object should be modified. If you simply exchange the first attribute of each Link object, it is not considered as reverse.

Hint3: It is guaranteed that the linked list is acyclic.

  • 你的实现应该修改原始链表。不要创建任何新的链表。

  • 我们所说的 reverse 是指每个 Link 对象的 rest 属性应该被修改。 如果你只是交换每个 Link 对象的 first 属性，这不被认为是 reverse。

  • 保证链表是无环的。