Как прочитать односвязный список в обратном направлении?

Question

Один из способов, который я могу придумать, - это перевернуть список и затем прочитать его. Но это включает в себя изменение списка, что плохо.
ИЛИ Я могу сделать копию списка и затем полностью изменить его, но для этого требуется дополнительная память O (n). Есть ли лучший метод, который не использует дополнительную память и не изменяет список и работает в O (N) время

код обратного связанного списка в c #

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

        while (current!=null)
        {
            nextNode = current.Next;
            current.Next = prev;
            prev=current;
            current = nextNode; 

        }
        head = prev;

}   

Рекурсивное решение

void ReadBackWard (Node n)
{
    if (n==null)
        return;
    else
        ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

Answer 1

Чтобы использовать O (n) память и производительность O (n), создайте стек; нажимайте на все, пока вы выполняете итерацию в прямом направлении, затем выталкивайте все, получая результаты.

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

Пример:

IEnumerable<T> Reverse (Node head) {
    Stack<Node> nodes = new Stack<Node>();
    while(head != null) {
        nodes.Push(head);
        head = head.Next;
    }
    while(nodes.Count > 0) {
        yield return nodes.Pop().Value;
    }
}

Answer 2

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

Как было указано ранее; если вам нужно пройти по списку в обе стороны; вам нужно иметь двусвязный список. Такова природа двусвязного списка, он идет в обе стороны.

Answer 3

На самом деле вы должны использовать двусвязный список.

Если это невозможно, я думаю, что лучшим вариантом будет создание копии списка, который был перевернут.

Другие параметры, такие как использование рекурсии (эффективное копирование списка в стек), могут привести к нехватке места в стеке, если список слишком длинный.

Answer 4

void reverse_print(node *head) 
{
    node *newHead = NULL, *cur = head;

    if(!head) return;

    // Reverse the link list O(n) time O(1) space
    while(cur){
        head = head->next;
        cur->next = newHead;
        newHead = cur;
        cur = head;
    }

    // Print the list O(n) time O(1) space
    cur = newHead;
    while(cur) {
        printf(" %d", cur->val);
        cur = cur->next;
    }

    // Reverse the link list again O(n) time O(1) space
    cur = newHead;
    while(cur){
        newHead = newHead->next;
        cur->next = head;
        head = cur;
        cur = newHead;
    }
    // Total complexity O(n) time O(1) space
}

Answer 5

Если вам не хватает памяти, вы можете перевернуть список, выполнить итерацию по нему и снова перевернуть его. В качестве альтернативы вы можете создать стек указателей на узлы (или что-то похожее на указатель в C #).

Answer 6

Существует третье решение, на этот раз с использованием O(log(n)) памяти и O(n log(n)) времени, таким образом занимая золотую середину между двумя решениями в ответе Марка.

Это, по сути, обратный спуск по порядку бинарного дерева [O(log(n))], за исключением того, что на каждом шаге вам нужно найти вершину дерева [O(n)]:

1. Разделить список на две части
2. Записаться во вторую половину списка
3. Вывести значение в средней точке
4. Рекурс в первую половину

Вот решение на Python (я не знаю C #):

def findMidpoint(head, tail):
  pos, mid = head, head
  while pos is not tail and pos.next is not tail:
    pos, mid = pos.next.next, mid.next
  return mid

def printReversed(head, tail=None):
  if head is not tail:
    mid = findMidpoint(head, tail)
    printReversed(mid.next, tail)
    print mid.value,
    printReversed(head, mid)

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

Например, для списка с миллионным входом три решения имеют порядок:

Solution   Memory       Performance
=========================================
 Marc #1     4MB    1 million operations
  Mine       80B    20 million operations
 Marc #2      4B    1 trillion operations

Answer 7

Вариант создания стека и помещения всех элементов в стек состоит в том, чтобы использовать рекурсию (и встроенный в систему стек), это, вероятно, не способ использовать производственный код, но служит лучшим (ИМХО) интервью ответьте по следующим причинам:

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

Answer 8

Предполагая, что ваш односвязный список реализует IEnumerable , вы можете использовать метод обратного расширения LINQ:

var backwards = singlyLinkedList.Reverse();

Вам понадобится добавить директиву using System.Linq; в верхней части файла кода, чтобы использовать методы расширения LINQ.

Answer 9

Если в программе Explicit Stack мы создадим стек только для данных каждого узла (вместо создания стека типа <Node>, мы создадим стек типа <T>), не будет ли это еще лучше? Потому что тогда нам не нужно хранить какую-либо другую информацию об Узле.

IEnumerable<T> Reverse (Node<T> head) {
    Stack<T> nodes = new Stack<T>();
    while(head != null) {
        nodes.Push(head.data);
        head = head.Next;
    }
    while(nodes.Count > 0) {
        yield return nodes.Pop();
    }
}

Answer 10

Что не так с:

    public void printBackwards(LinkedList sl){    
        ListIterator<Element> litr = sl.listIterator(sl.size());
        Element temp;
        while(litr.previousIndex() >= 0){
            temp = litr.previous();
            System.out.println(temp);
        }
    }

O (n) производительность, O (1) память и просто как do-re-mi!