python - 算法可以将列表项反转到位？

我正在我的CS课程中学习数据结构和算法效率，我创建了一个算法来返回一个新的项目列表，该列表与原始列表的顺序相反。我正在尝试用递归的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，对吗？

最佳答案

你的案子很好。它在两种通常意义上都是“到位”的。它修改与传入的列表相同的列表，并且除了传入的列表外，它只使用恒定的内存量。
你的一般情况是你有问题。它使用了大量的额外内存（递归的N／2级，每个都在递归调用中持有两个列表，所以所有级别的所有这些列表都必须同时存在），并且它不修改传入的列表（而是返回一个新的列表）。
我不想为您做太多的工作，但是解决这个问题的关键是在递归步骤中传递一个（或者两个，如果您愿意的话）。函数的可选参数，或定义具有这些参数的递归帮助函数。使用此选项可指示要反转的列表区域。
正如评论中提到的，CPython没有尾部递归优化。这意味着，使用这种调用递归的算法永远不会真正“就位”，因为它将使用线性堆栈量。但是“就地”在“修改原始列表而不是返回新列表”的意义上肯定是可行的。