我要寻找的反转给定名单的同一个实例，为O（1）额外的空间和O（n）时间的方法。 这不是硬件和我在找一些库的方法做的工作对我来说，因为这仅仅是一个锻炼自己，以纯好奇。 任何想法如何为O做（1）额外的空间和O（n）的时间？ （如果可能的话，而不反射为好）？ 签名公开＆LT; T＆GT; void反转（名单＆LT; T＆GT;清单）。 （*）假设获得（），以列表的头和尾是O（1），但它的中间是O（n）。 我想出了一个递归的解决方案，但它是O（n）的空间，O（n）的时间

I am looking for a method that reverses the same instance of a given list, with O(1) additional space and O(n) time. this is not HW nor I am looking for some library method to do the job for me, as this is only an exercise for myself, and out of pure curiousity. any ideas how to do it with O(1) additional space and O(n) time? (and if possible without reflection as well)? signature is public <T> void reverse(List<T> list). (*)assume get() to the head and tail of the list is O(1), but to the middle of it is O(n). I came up with a recursive solution, but it is O(n) space, O(n) time

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解决方案，为名单，其中，T＆GT; ，只有在实现的假设是访问时间O（1）对于头部和尾部，并使用名单，其中，T＆GT; 接口

I am looking for a java solution, for List<T>, only assumption on implementation is access time O(1) for head and tail, and using List<T> interface.

推荐答案

刚看完以下步骤之一。这是你在​​谈论的东西。

Just read one of the following. It is the thing you're talking about.

请注意，我们谈论的是单链接列表中。

Please note that we're talking about singly 'linked' lists.

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

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

http://www.geekpedia.com/$c$c48_Reverse-a-linked-list.html

http://www.$c$cproject.com/KB/recipes/ReverseLinkedList.aspx

另外给你一个额外的问题：

Plus an extra question for you:

你会如何找到 N 日从链表假设它的尾部元素单链表，你只有头指针为O（1）空间和O（ N）的时间？

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?