如何向后阅读单链表？

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

你真的应该使用双向链表.

如果这是不可能的,我认为你最好的选择是构建一个已被反转的列表的副本.

其他选项,例如依赖递归(有效地将列表复制到堆栈)可能会导致如果列表太长则耗尽堆栈空间.