反转列表项的算法？

Question

我现在正在学习我的 CS class 中的数据结构和算法效率，并且我已经创建了一个算法来 return 一个新的项目列表，这些项目的顺序与原始列表。我试图弄清楚如何使用递归在 Python 列表中执行此操作，但解决方案让我望而却步。这是我的代码：

def reverse_list(in_list):
    n = len(in_list)
    print('List is: ', in_list)
    if n <= 2:
        in_list[0], in_list[-1] = in_list[-1], in_list[0]
        return in_list
    else:
        first = [in_list[0]]
        last = [in_list[-1]]
        temp = reverse_list(in_list[1:-1])
        in_list = last + temp + first
        print('Now list is: ', in_list)
        return in_list

if __name__ == '__main__':
    list1 = list(range(1, 12))
    list2 = reverse_list(list1)
    print(list2)

附带说明一下，这是 O(n) 的平均情况，因为它 n/2 对吗？

Answer 1

你的 n <= 2 情况很好。它在两种通常意义上都是 "in-place" 。它修改传入的列表，除了传入的列表外，它只使用恒定数量的内存。

你的一般情况就是你有问题的地方。它使用大量额外的内存（n/2 级递归，在递归调用中每个级包含两个列表，因此所有级别的所有列表都必须同时存在），并且它不会修改传递的列表在（而是 returns 一个新列表）。

我不想为你做太多，但解决这个问题的关键是将一个（或两个，如果你愿意的话）额外参数传递到递归步骤中。您的函数的可选参数，或定义具有它们的递归辅助函数。使用它来指示 列表的哪个区域 就地反转。

正如有人在评论中提到的，CPython 没有尾递归优化。这意味着没有像这样使用调用递归的算法会成为真正的 "in-place"，因为它将使用线性数量的堆栈。但是 "modifies the original list instead of returning a new one" 意义上的 "in-place" 当然是可行的。

Answer 2

你真的不想在这里使用递归，因为它并没有真正简化函数调用所涉及的额外开销的问题：

list3 = list(range(1, 10))
for i in range(len(list3)/2):
    list3[i], list3[len(list3)-i-1] = list3[len(list3)-i-1], list3[i]
print(list3)

如果您想使用递归来处理它，您需要将索引计数器传递给您的函数的每次调用，直到您完成列表的一半。这会给你 O(n/2) 运行时间。

反转列表项的算法？

Algorithm to reverse list items in place?

python

reverse