如何在O(1)空间和O(n)时间内翻转一个列表？

Question

我正在寻找一种方法，可以在O（1）的额外空间和O（n）的时间内反转给定列表的同一实例。 这不是作业，也不是在寻找某个库方法来完成任务，因为这只是我自己的练习，出于纯粹的好奇心。 有什么想法可以用O（1）的额外空间和O（n）的时间做到吗？ （如果可能，也不要使用反射）？ 签名是public <T> void reverse(List<T> list)。 （*）假设获取列表的头部和尾部是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>接口。

- amit

---

你不能简单地从0迭代到n/2并交换i和n-i吗？在for循环中，而不是foreach... - Max

你不能仅仅假设它是一个Java的List<T>；这样做并不能让你对类型进行约束（例如，你不能假设索引是O(n)或其他），甚至可能根本无法修改列表。 :-) - Donal Fellows

@Donal：嘿，但你至少可以编写符合Java（TM）规范的代码来实现它——反转列表或<s>不断尝试</s>抛出UnsupportedOperationException异常。此外，文档中指出对于List，索引“可以”是线性时间。因此它可能会更快，但我认为我们应该通过省略推断它不可能更慢，因此它是O(n)。 - Steve Jessop

@amit：在这种情况下，我认为你应该询问关于单向链表的问题，而不是询问关于“List”接口的问题，因为我认为它很清楚地表示“最坏”的情况是双向链表。 - Steve Jessop

我重新考虑了这个解决方案，如果我将递归改为循环+堆栈（从而减少递归的内存使用），那么解决方案仍然是O(n)的额外内存吗？我认为不是，因为每次我将一个元素推入堆栈时，我会从列表中删除一个元素，所以在算法的每个阶段，总体上|Stack|+|List| <= n+1。你有什么想法吗？ - amit

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

另外还有一个问题：

假设你只有头指针，并且时间复杂度为O（N），空间复杂度为O（1），如何从链表尾部找到第 N 个元素？

- ahmet alp balkan

---

@ahmet：只需对列表进行两次遍历。首先找到长度，然后减去它以获取索引，再从开头重新遍历以找到该索引。O(2n) = O(n). - hammar

@ahmet，更快的解决方案是：从列表头开始使用指针遍历N个元素，然后添加第二个指针，并使用两个指针遍历（平均递增），直到第一个指针到达末尾。 - davin

@ahmet：我知道使用节点的解决方案，但我想看看是否有什么我错过了，或者说，只使用List接口，我想做的事情是不可能的...不过你提供的链接很好，谢谢。 :) - amit

不是真的。使用ikegami的方法，->next的数量为size-N或2size-N。使用davin的方法：N+2(size-N)=2*size-N。ikegami的方法至少和davin的方法一样好，如果列表跟踪其大小，则更好。奖励：ikegami的方法应该导致较少的缓存未命中。 - ikegami

如果您事先不知道大小，并且关心缓存未命中，那么更快的解决方案（就下一次访问而言）是跟踪每N个节点的最后两个，当您到达末尾时，请返回并遍历最后至多2N个项目。假设“推送新指针”可以在寄存器中完成且时间可以忽略不计，则最多只需要n + N个下一个访问，而davin和ikegami的解决方案都需要2n-N个访问。 - eivour

Answer 2

使用List迭代器:

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);
}

- ratchet freak

---

previousIndex() 太容易了，不做它太亏了。但是在单向链表上，previous 确实无法以 O(1) 的时间复杂度完成，虽然有一些方法可以在 O(n) 时间和 O(1) 空间内反转单向链表，但这些方法非常特定（从源中弹出并推到目标），而基于数组的列表将在相同的算法上运行 O(n^2) 和/或 O(n) 内存，具体取决于算法是否需要移动数组或预分配目标。 - ratchet freak

你不需要使用 previousIndex()。你可以保留自己的计数器。但是，从 LinkedList 返回的列表迭代器具有 O(1) 的 previousIndex() 实现。 - erickson

@ahmet - 你在哪里看到不稳定的空间要求？ - erickson

@amit：我认为我们可以假设（请查看我在主问题下面的评论）。Java的List接口在复杂度方面缺乏明确规定，但是如果我们不能假设previous和/或previousIndex是O(1)的（因为它可能是单向链表），那么我们也不能假设next或nextIndex也是O(1)的（因为它可能是反向单向链表）。通过阅读文档中的一些信息，我认为List必须是双向而不是单向链表。 - Steve Jessop

@ratchet：是的，这就是我最初说的。在所有常识中，我们必须假设它，但我们必须读懂其中的含义，因为Java文档未能正式说明。这些友好的Sun技术人员试图以对话的方式进行交流。Oracle可能会采取更多的“告诉你，你试试看我们是否起诉你”的路线;-) - Steve Jessop

Answer 3

你已经知道长度了。所以只需使用1个临时变量，从索引0开始交换list[0]和list[length-1]，然后交换list[1]和list[length-2]，以此类推。对于1个临时变量，时间复杂度为O(n)，空间复杂度为O(1)。

编辑：刚刚注意到你假设访问列表中间的时间复杂度为O(n)。好吧。不用在意。

或者，如果是双向链表，则存储您交换的两个元素的下一个/上一个指针，向中间移动。这样可以获得O(n)的时间复杂度。

- Botz3000

---

他说的是列表，不是数组。 - ahmet alp balkan

使用list[length-i]进行交换，其中i->n/2的时间复杂度为O(n)，因此这种解决方案将使时间复杂度变为O(n^2)。 - amit

是的，正如我所提到的，我刚刚注意到你无法在常数时间内随机访问它。请参见编辑。 - Botz3000

这可以使用双向链表和两个指针来实现。空间复杂度为O(1)，时间复杂度为O(n)。 - davin

修改了问题，我正在寻找List < T >接口的Java实现。 - amit

Answer 4

像归并排序或快速排序这样的比较排序算法，您可以获得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;

- J. Michael Wuerth

Answer 5

如讨论所述，在一般情况下这是不可行的，您需要对单个操作的复杂性做出一些假设。如果您的迭代器具有常数时间的next()和previous()，请使用已经给出的解决方案。它应该适用于LinkedList和ArrayList。

我考虑了一个适用于单向链表的解决方案（但不适用于类似ArrayList的东西），但遗憾的是ListIterators add方法在光标之前而不是之后插入元素，因此不能使用List + ListIterator接口（如果我们无法修补ListIterator实现以缓存预插入元素以允许在O(1)中进行单个previous()之后的add）。

在这里，假设有一个简单的带有下一个指针的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<T> list) {
    int index = list.size() -1;
    while(n > 0) {
       T element = list.remove(0);
       list.add(n, element);
       n--;
    }
}

在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();
    }
}

当然，通常的单向链表实现不会有O(1)的previous实现，因此在那里它将无法工作，如前所述。（并且它们可能会抛出ConcurrentModificationException异常，或返回错误的previousIndex。）

- Paŭlo Ebermann

Answer 6

这里是一个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;
    }
}

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 

希望有所帮助 :)

- Prashant Mishra

---

使用Java的列表接口进行工作的想法。 - Eduardo Sebastian

Answer 7

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);
}

即使在链表上，这个操作的时间复杂度也应该是线性的。

- Donal Fellows

---

你从我这里得到了那个，这是一个几乎完美的代码复制 ;) - ratchet freak

Answer 8

   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;
}

- sa_nyc

---

这似乎是O(n)空间，因为递归调用的堆栈跟踪，而问题要求O(1)空间。 - amit