как перевернуть список с O (1) пробелом и O (n) временем?

Question

Я ищу метод, который переворачивает тот же экземпляр данного списка, с O (1) дополнительным пробелом и O (n) временем.
это не HW, и я не ищу какой-то библиотечный метод, который бы выполнял эту работу за меня, поскольку это всего лишь упражнение для меня, и из чистого любопытства

есть идеи, как это сделать с 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)?

Answer 2

с использованием 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);
}

Answer 3

Вы уже знаете длину. Так что просто используйте 1 временную переменную и начните с индекса 0 и перейдите к списку обмена [0] и списку [длина -1], затем списку [1] и списку [длина-2], и так далее. O (n) время и O (1) место для 1 временной переменной.

РЕДАКТИРОВАТЬ: только что заметил, что вы принимаете O (n) для доступа к середине списка. Ну что ж. фига.

альтернативно, сохраните следующие / предыдущие указатели двух элементов, которые вы поменяли местами, чтобы переместиться к середине (при условии, что это двусвязный список). Тогда вы получите O (N) время.

Answer 4

Вот решение на 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 

Надеюсь, это поможет :)

Answer 5

Наилучшая производительность, которую вы можете получить от сортировок сравнения, таких как сортировка слиянием или быстрая сортировка, - это O (nlogn). Вы можете получить производительность O (n) от несопоставимых сортировок, таких как радикальная сортировка.

Если вы переворачиваете связанный список, вы можете перевернуть список за O (n) раз, используя всего 3 дополнительных элемента. Вам нужно 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;

Answer 6

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

Answer 7

Как уже говорилось, в общем случае это невозможно, нужно предположить что-то относительно сложности отдельных операций.Если у вас есть постоянное время next() и previous() для итераторов, используйте уже данное решение.Он должен работать как для LinkedList, так и для ArrayList.

Я думал о решении, которое будет работать для односвязного списка (но не для чего-то вроде ArrayList), но, к сожалению, метод ListIterators add вставляет элемент передкурсор вместо того, чтобы после него, таким образом, это не выполнимо с интерфейсами List + ListIterator (если мы не можем исправить реализацию ListIterator, чтобы кэшировать элемент предварительной вставки, чтобы позволить один previous() после add в O (1))).

Здесь предполагается простой класс 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.)

Answer 8

Интерфейс ListIterator - это то, что вы ищете (при разумном предположении, что рассматриваемый список полностью его поддерживает; и ArrayList, и LinkedList do):

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

Даже в связанных списках, оно должно быть линейным по времени.