Как изменить список с O (1) пространством и временем O (n)?

Ответ 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)?

Ответ 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);
}

Ответ 3

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

EDIT: Только что вы заметили, что вы используете O (n) для доступа к середине списка. Ну что ж. фига.

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

Ответ 4

Интерфейс 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);
}

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

Ответ 5

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

Я подумал о решении, которое будет работать для односвязного списка (но не для чего-то вроде ArrayList), но, к сожалению, метод ListIterators add вставляет элемент перед курсором, а не после него, поэтому он не выполним с интерфейсами List + ListIterator (если мы не можем исправить реализацию ListIterator для кэширования элемента pre-insert, чтобы разрешить одиночный 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 или возвращать erronous previousIndex.)

Ответ 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;
    }
}

Выход программы:

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 

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

Ответ 7

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

Если вы перевернули связанный список, вы можете отменить список в 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;

Ответ 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;
}