Реверс-печать односвязного списка

Question

Кто-нибудь знает, как распечатать односвязный список в обратном порядке (один проход и фиксированный и не зависит от количества элементов ОЗУ).

Answer 1

Мой ответ.Там нет ответа, который решает это к вашим спецификациям.Это не может быть несколько проходов, это не может быть рекурсивно (что я считаю одним), это должна быть постоянная память ...

Не думаю, что вы найдете решение, и люди,сказал, что вы могли бы сделать это, очевидно, есть некоторая хитрость аспекта вопроса.Они явно не используют тот же набор определений, который использует это сообщество.

Answer 2

Я думаю, что вы можете сделать это за время O (n) и пространство O (1), но технически это не «один проход».

печать: O (n) перевернуть обратно связанный список: O (n)

Answer 3

Эта опция предполагает, что вы знаете количество (если это не один проход уже пройден), или если вы не можете использовать один проход, тогда просто установите для счетчика какое-то разумное большое максимальное максимальное значение верхнего предела. .

long count = 10000; // set this to whatever the count is, or calcualte it
string filename = @"c:\foo.out";
using (StreamWriter writer = new StreamWriter(filename))
{
    int index = 0;
    long maxLength = 12; // set this to the max length of an item + 2 (for /r/n)
    while(values.Next())
    {
        writer.BaseStream.Seek(maxLength * (count - index - 1), SeekOrigin.Begin);
        writer.WriteLine(values[index].ToString().PadLeft(maxLength));
        writer.Flush();
        index++;
    }
}

Вывод будет в файле c:\foo.out, дополненном пробелами. Поскольку в вопросе не указывалось, где нужно выводить данные или в каком формате должен быть вывод (например, не включать пустые строки заранее). Учитывая, что это связанный список, длина может быть очень большой (>int.MaxValue), так что запись вывода в файл является вполне приемлемым транспортным форматом.

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

Ответом на этот ответ будет то, что вы не можете seek в обратном направлении в выходном потоке, затем просто напечатаете \r возвращаемый символ и ищите в обратном направлении таким образом, не получая ответа от интервьюера, спрашивающего, идентифицируете ли вы или встречаетесь Невозможные требования являются частью описания работы.

Answer 4

String s ="";
for(each element el in list)
     s=el.data+", "+s;
 println(s);

Это один проход.

Answer 5

Вот решение с java.util.LinkedList. Память остается той же самой, так как вы удаляете и добавляете элемент в тот же список.Я думаю, разумно предположить, что любая достойная реализация односвязного списка будет отслеживать его размер, голову и хвост.

import java.util.Arrays;
import java.util.LinkedList;

class PrintReverse {
    public static void main(String[] args) {
        Integer[] array = {1, 2, 3, 4};
        LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(array));
        System.out.println(list);
        printListBackward(list);
    }

    public static void printListBackward(LinkedList<Integer> list) {
        int size = list.size();

        for (int i = 0; i < size; i++) {
            Integer n = list.removeLast();
            list.push(n);
            System.out.println(n.toString());
        }
        System.out.println(list);

    }
}

, который выдает следующий результат ...

[1, 2, 3, 4]
4
3
2
1
[1, 2, 3, 4]

Что ты думаешь?

Answer 6

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

Answer 7

Пройдите по односвязному списку и поместите каждый элемент в стек. Сдвигайте стопку до тех пор, пока она не опустеет, одновременно распечатывая каждый всплывающий элемент.

node  = head of node list
stack = new Stack()

while ( node is not NULL )
{
    stack.push( node.data )
    node = node.next
}

while ( !stack.empty() )
{
    print( stack.pop() )
}

Answer 8

Импорт в массив, печать массива в обратном порядке.

Answer 9

void printList(listItem node) {
    if (node.next != null) {
        printList(node.next);
    }

    echoOrSystemOutPrintlnOrPrintfOrWhatever(node.data);
}

printList(rootNode);

Answer 10

Ну, вы не сказали, что это должно быть эффективно. (К тому же, вероятно, нет более эффективной реализации постоянной памяти.) Кроме того, как отметили комментаторы, это однопроходный режим, только когда length(list) == 1.

void printReversedLinkedList(listptr root) {
    listptr lastPrinted = null;
    while (lastPrinted != root) {
        listptr ptr = root;  // start from the beginning of the list
        // follow until next is EoL or already printed
        while (ptr->next != null && ptr->next != lastPrinted)
            ptr = ptr->next;
        // print current node & update last printed
        printf("%s", ptr->data);
        lastPrinted = ptr;
    }

Постоянная память, эффективность O (n ^ 2).