java - 如何反转具有 O(1) 空间和 O(n) 时间的列表？

Question

我正在寻找一种方法来反转给定列表的相同实例，具有 O(1) 额外空间和 O(n) 时间。
这不是硬件，我也不是在寻找一些图书馆方法来为我完成这项工作，因为这只是我自己的一个练习，而且纯粹是出于好奇。

有什么想法可以用 O(1) 的额外空间和 O(n) 的时间来实现吗？ (如果可能的话，也不要反射(reflection))？
签名是public <T> void reverse(List<T> list) .

(*)假设 get() 到列表的头部和尾部是 O(1)，但到它的中间是 O(n)。

我想出了一个递归的解决方案，但是是O(n)空间，O(n)时间

public <T> void reverseAux(List<T> list,int size) {
    if (size == 0) return;
    T elem = list.remove(size-1);
    reverseAux(list,size-1);
    list.add(0,elem);
}
public <T> void reverse(List<T> list) {
    reverseAux(list, list.size());
}

编辑: 我正在为 List<T> 寻找 java 解决方案, 唯一的实现假设是头部和尾部的访问时间 O(1)，并使用 List<T>界面。

Answer 1

只需阅读以下内容之一。这就是您所说的。

请注意，我们讨论的是单“链接”列表。

http://www.teamten.com/lawrence/writings/reverse_a_linked_list.html

http://www.mytechinterviews.com/reverse-a-linked-list

http://www.geekpedia.com/code48_Reverse-a-linked-list.html

http://www.codeproject.com/KB/recipes/ReverseLinkedList.aspx

还有一个问题要问你:

How would you find Nth element from the tail of a linked list assuming it is singly linked and you have only head pointer with O(1) space and O(N) time?