如何用O（1）空间和O（n）时间反转列表？
我正在寻找一种方法来反转给定列表的相同实例，具有O（1）额外空间和O（n）时间。
这不是硬件，也不是我正在寻找一些图书馆方法为我做这项工作，因为这只是我自己的练习，而且出于纯粹的好奇心。
任何想法如何使用O（1）额外的空间和O（n）时间？ （如果可能的话，没有反思）？
签名是public void reverse(List list) 。
（*）假设列表的头部和尾部的get（）是O（1），但是它的中间是O（n）。
我提出了一个递归解决方案，但它是O（n）空间，O（n）时间
public void reverseAux(List list,int size) { if (size == 0) return; T elem = list.remove(size-1); reverseAux(list,size-1); list.add(0,elem); } public void reverse(List list) { reverseAux(list, list.size()); }
编辑：我正在寻找一个java解决方案，对于List ，只有实现的假设是头部和尾部的访问时间O（1），并使用List接口。
只需阅读以下内容之一即可。 这是你在谈论的事情。
请注意，我们正在谈论单独的’链接’列表。
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）时间？
使用ListIterators：
ListIterator head = list.listIterator(); ListIterator 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()
你已经知道了长度。 所以只需使用1个临时变量并从索引0开始，继续交换列表[0]并列出[length -1]，然后列出[1]并列出[length-2]，依此类推。 O（n）时间和O（1）空间为1个临时变量。
编辑：刚刚注意到你假设O（n）访问列表的中间位置。 好吧。 没关系。
或者，存储你交换的两个元素的下一个/前一个指针向中间移动（假设它是一个双向链表）。 然后你得到O（n）时间。
这是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"); }
完整代码如下：
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; } }
程序的输出：
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
希望能帮助到你 ：）
ListIterator接口是你正在寻找的（在合理的假设下，有问题的列表完全支持它; ArrayList和LinkedList都这样做）：
ListIterator fwd = list.listIterator(); ListIterator back = list.listIterator(list.size()); while (fwd.nextIndex() < back.previousIndex()) { T tmp = fwd.next(); fwd.set(back.previous()); back.set(tmp); }
即使在链表上，这也应该是线性的。
如上所述，在一般情况下，这是不可行的，您需要假设某些操作的复杂性。 如果迭代器有常量时间next()和previous() ，请使用已经给出的解决方案。 它应该适用于LinkedList和ArrayList。
我想到了一个适用于单链表的解决方案（但不适用于像ArrayList这样的东西），但遗憾的是ListIterators add方法在光标之前而不是之后插入元素，因此List + ListIterator无法实现接口（如果我们无法修补ListIterator实现来缓存预插入元素以允许在O（1）中add后的单个previous() ））。
这里，假设一个带有下一个指针的简单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; } }
在索引术语中，这将是这样的：
public void reverseList(List list) { int index = list.size() -1; while(n > 0) { T element = list.remove(0); list.add(n, element); n--; } }
在ListIterator术语中，这将是这样的：
public void reverseList(List list) { ListIterator 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(); } }
当然，通常的单链表实现将不具有O（1） previous实现，因此它将不在那里工作，如前所述。 （并且它们可能抛出ConcurrentModificationException，或返回错误的previousIndex 。）
从合并排序或快速排序等比较排序中获得的最佳性能是O（nlogn）。 您可以通过基数排序等非比较排序获得O（n）性能。
如果要反转链接列表，则可以使用仅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;
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; }