java 如何反转具有 O(1) 空间和 O(n) 时间的列表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5985365/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
how to reverse a list with O(1) space and O(n) time?
提问by amit
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
我正在寻找一种方法来反转给定列表的相同实例，具有 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());
}
EDIT: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.
编辑：我正在寻找一个 java 解决方案，对于List<T>实现的唯一假设是头部和尾部的访问时间 O(1)，并使用List<T>接口。
采纳答案by AhmetB - Google
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.teamten.com/lawrence/writings/reverse_a_linked_list.html
http://www.mytechinterviews.com/reverse-a-linked-list
http://www.mytechinterviews.com/reverse-a-linked-list
http://www.geekpedia.com/code48_Reverse-a-linked-list.html
http://www.geekpedia.com/code48_Reverse-a-linked-list.html
http://www.codeproject.com/KB/recipes/ReverseLinkedList.aspx
http://www.codeproject.com/KB/recipes/ReverseLinkedList.aspx
Plus an extra question for you:
还有一个额外的问题给你：
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?
N假设它是单链接的并且您只有 O(1) 空间和 O(N) 时间的头指针，您将如何从链表的尾部找到第 th 个元素？
回答by ratchet freak
using ListIterators:
使用列表迭代器：
ListIterator<T> head = list.listIterator();
ListIterator<T> tail = list.listIterator(size);//assuming this can be done in O(1) though O(n) doesn't hurt that much and total is still O(n)
while(head.nextIndex()<tail.previousIndex()){
T tmp = head.next();
head.set(tail.previous());
tail.set(tmp);
}
回答by Botz3000
You already know the length. So just use 1 temporary variable and start at index 0 and go on swapping list[0] and list[length -1], then list[1] and list[length-2], and so on. O(n) time and O(1) space for 1 temporary variable.
你已经知道长度了。因此，只需使用 1 个临时变量并从索引 0 开始，然后继续交换 list[0] 和 list[length -1]，然后是 list[1] 和 list[length-2]，依此类推。1 个临时变量的 O(n) 时间和 O(1) 空间。
EDIT: Just noticed you assume O(n) for accessing the middle of the list. oh well. nevermind.
编辑：刚刚注意到您假设 O(n) 用于访问列表的中间。那好吧。没关系。
alternatively, store the next/previous pointers of the two elements you swapped to move towards the middle (assuming it's a doubly linked list). Then you get O(n) time.
或者，存储您交换以向中间移动的两个元素的下一个/上一个指针（假设它是一个双向链表）。然后你得到 O(n) 时间。
回答by Prashant Mishra
Here is a solution in Java, with O(n) time complexity (just a single pass) and O(1) space complexity (Using just two temporary variables):
这是 Java 中的一个解决方案，时间复杂度为 O(n)（仅通过一次）和空间复杂度为 O(1)（仅使用两个临时变量）：
private static void reverseLinkedList() {//O(n) Time complexity, O(1) space complexity
//two temp pointers
Node next = null, previous = null;
while(head.next != null){
next = head.next;//move next to next address
head.next = previous; //previous node will be the next node for head, so that head will point reverse
previous = head; //incrementing previous to the current node
head = next; //incrementing head
}
//at this point head points to last node and previous has the remaining reversed array
head.next = previous;
System.out.println("\nReversed");
}
Full code goes like:
完整代码如下：
package com.test;
public class LinkedListReverse {
private static Node head;
public static void main(String[] args) {
for(int i = 0 ; i< 10 ; i++){
addToLinkedList(i);
}
System.out.println("Added Data");
printLinkedList();
reverseLinkedList();
printLinkedList();
}
private static void reverseLinkedList() {//O(n) Time complexity, O(1) space complexity
//two temp pointers
Node next = null, previous = null;
while(head.next != null){
next = head.next;//move next to next address
head.next = previous; //previous node will be the next node for head, so that head will point reverse
previous = head; //incrementing previous to the current node
head = next; //incrementing head
}
//at this point head points to last node and previous has the remaining reversed array
head.next = previous;
System.out.println("\nReversed");
}
/* Logic for adding and printing linked list*/
private static void printLinkedList() {
System.out.println("Printing linked list");
Node temp = head;
while(temp.next != null){
System.out.print(temp.value+" ");
temp = temp.next;
}
System.out.print(temp.value+" ");//print the value at the last node
}
private static void addToLinkedList(int value){
if(head == null){
head = new Node(value, null);
}else{
Node temp = head;
while(temp.next != null){
temp = temp.next;
}
temp.next = new Node(value, null);
}
}
}
//Linked List definition
class Node{
int value;
Node next;
public Node(int value, Node next){
this.value = value;
this.next = next;
}
}
Program's Output:
程序的输出：
Added Data
Printing linked list
0 1 2 3 4 5 6 7 8 9
Reversed
Printing linked list
9 8 7 6 5 4 3 2 1 0
Hope it helps :)
希望能帮助到你 ：）
回答by J. Michael Wuerth
The best performance you can get from comparison sorts like merge sort or quick sort is O(nlogn). You can get O(n) performance from non-comparison sorts like radix sort.
从比较排序（如合并排序或快速排序）中可以获得的最佳性能是 O(nlogn)。您可以从非比较排序（如基数排序）中获得 O(n) 性能。
If you are reversing a linked-list, then you can reverse the list in O(n) time with using just 3 extra items. You need 3 pointers to keep track of what you're currently pointing to, what is before your current item and what is after your current item. The code is:
如果要反转链表，则只需使用 3 个额外项即可在 O(n) 时间内反转链表。您需要 3 个指针来跟踪当前指向的内容、当前项目之前的内容以及当前项目之后的内容。代码是：
Node current = head;
Node next = null;
Node prev = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
回答by Donal Fellows
The ListIteratorinterface is what you're looking for (under the reasonable assumption that the list in question fully supports it; both ArrayListand LinkedListdo):
该ListIterator接口是你在找什么（在合理的假设，在问题名单完全支持它下;既ArrayList和LinkedList做的）：
ListIterator<T> fwd = list.listIterator();
ListIterator<T> back = list.listIterator(list.size());
while (fwd.nextIndex() < back.previousIndex()) {
T tmp = fwd.next();
fwd.set(back.previous());
back.set(tmp);
}
Even on linked lists, this should be linear in time.
即使在链表上，这也应该是线性的。
回答by Pa?lo Ebermann
As discussed, in the general case this is not doable, you need to assume something about the complexity of the individual operations. If you have constant-time next()and previous()for the iterators, use the solution already given. It should work for both LinkedList and ArrayList.
正如所讨论的，在一般情况下这是不可行的，您需要对单个操作的复杂性进行一些假设。如果您有常数时间next()和previous()迭代器，请使用已经给出的解决方案。它应该适用于 LinkedList 和 ArrayList。
I thought about a solution which would work for a singly-linked list (but not for something like ArrayList), but sadly the ListIterators addmethod inserts the element before the cursor instead of after it, thus it is not doable with the List + ListIterator interfaces (if we can't patch the ListIterator implementation to cache the pre-insert element to allow a single previous()after addin O(1)).
我想到了一个适用于单链表的解决方案（但不适用于 ArrayList 之类的东西），但遗憾的是 ListIteratorsadd方法在光标之前而不是在光标之后插入元素，因此它不适用于 List + ListIterator 接口（如果我们不能修补 ListIterator 实现来缓存 pre-insert 元素以在 O(1) 中允许单个previous()after add）。
Here, assuming a simple Nodeclass with next-pointer:
在这里，假设一个Node带有下一个指针的简单类：
/**
* reverses a singly linked list.
* @param first the fist node. This will be the new last node.
* @param last the last node. This will be the new first node.
*/
void reverseList(Node first, Node last) {
while(first != last) {
Node temp = first;
first = temp.next;
temp.next = last.next;
last.next = temp;
}
}
In index terms, this would be something like this:
在索引方面，这将是这样的：
public void reverseList(List<T> list) {
int index = list.size() -1;
while(n > 0) {
T element = list.remove(0);
list.add(n, element);
n--;
}
}
In ListIterator terms, this would be something like this:
在 ListIterator 术语中，这将是这样的：
public void reverseList(List<T> list) {
ListIterator<T> it = list.listIterator(list.size());
while(it.previousIndex() > 0) { // we could count ourself here, too
T element = list.remove(0);
it.add(element);
it.previous();
}
}
Of course, usual singly linked list implementations will not have a O(1) previousimplementation, thus it will not work there, as said before. (And they might throw a ConcurrentModificationException, or return erronous previousIndex.)
当然，通常的单链表实现不会有 O(1)previous实现，因此它不会在那里工作，如前所述。（他们可能会抛出 ConcurrentModificationException，或者返回错误的previousIndex。）
回答by sa_nyc
public LinkedList Reverse(LinkedList head)
{
if (head == null) return null; // first question
if (head.Next == null) return head; // second question
// third question
// so we grab the second element (which will be the last after we reverse it)
LinkedList secondElem = head.Next;
// bug fix - need to unlink list from the rest or you will get a cycle
head.Next = null;
// then we reverse everything from the second element on
LinkedList reverseRest = Reverse(secondElem);
// then we join the two lists
secondElem.Next = head;
return reverseRest;
}
