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

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

11 голосов
/ 12 июля 2009

Один из способов, который я могу придумать, - это перевернуть список и затем прочитать его. Но это включает в себя изменение списка, что плохо.
ИЛИ Я могу сделать копию списка и затем полностью изменить его, но для этого требуется дополнительная память 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);

}

Ответы [ 13 ]

0 голосов
/ 20 июля 2009

Это грязно, но работает: 

class SinglyLinkedList {
SinglyLinkedList next;
int pos;
SinglyLinkedList(int pos) {
    this.pos = pos;
}
SinglyLinkedList previous(SinglyLinkedList startNode) {
    if (startNode == this) return null;
    if (startNode.next == this) return startNode;
    else return previous(startNode.next);
}

static int count = 0;
static SinglyLinkedList list;
static SinglyLinkedList head;
static SinglyLinkedList tail;
public static void main (String [] args) {
    init();

    System.out.println("Head: " + head.pos);
    System.out.println("Tail: " + tail.pos);

    list = head;
    System.out.print("List forwards: ");
    while (list != null) {
        System.out.print(list.pos + ",");
        list = list.next;
    }

    list = tail;
    System.out.print("\nList backwards: ");
    while (list.previous(head) != null) {
        System.out.print(list.pos + ",");
        list = list.previous(head);
    }
}
static void init() {
    list = new SinglyLinkedList(0);
    head = list;
    while (count < 100) {
        list.next = new SinglyLinkedList(++count);
        list = list.next;
    }
    tail = list;
}

}

0 голосов
/ 12 июля 2009

вы можете прочитать его в O (n ^ 2) - каждый раз, когда вы читаете последний узел и распечатываете предыдущий

0 голосов
/ 12 июля 2009

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

Это, конечно, ужасно плохо с точки зрения производительности.

Я уверен, что у некоторых умных людей есть лучшее решение.

Псевдокод (даже с ошибками): 

current node = nothing
while current node is not first node
    node = start
    while node is not current node
        previous node = node
        node = next node
    produce previous node
    set current node to previous node
Страница:
...