如何用O(1)空间和O(n)时间反转列表？

Question

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

任何想法如何用O(1)额外的空间和O(n)时间？(如果可能的话,没有反思)？
签名是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());
}

编辑:我正在寻找一个java解决方案,因为List<T>,只有实现的假设是头部和尾部的访问时间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

另外还有一个问题:

你如何N从链表的尾部找到元素,假设它是单链接的,你只有头指针有O(1)空间和O(N)时间？