如何向后读取单向链表？ [英] How to read a singly linked list backwards?

问题描述

这是我能想到的一个方法是扭转列表，然后阅读。
但这涉及更改列表，它是坏的。

或我可以让列表的副本，然后扭转它，但这种使用额外的O（n）的内存。
是有不使用额外的内存并且不修改列表，并运行在O没有更好的方法（n）时间

反向链接列表代码是这样的，在c＃

  void反转（节点头）
 {
节点上一个= NULL; 
节点电流=头; 
节点nextNode = NULL; 
 
，而（电流！= NULL）
 {
 nextNode = current.Next; 
 current.Next =上一页; 
 =上一张电流; 
电流= nextNode; 
 
} 
 =头上一页; 
 
} 
  

递归的解决方案是

 无效ReadBackWard（节点N）
 {
如果（N == NULL）
的回报; 
，否则
 ReadBackward（n.Next）; 
 
 Console.WriteLine（n.Data）; 
 
} 
  

解决方案

要使用O（n）的内存和O（n）性能，创建一个堆栈;推上的一切，你在向前方向迭代，然后弹出事事休，产生的结果。

要使用为O（n ^ 2）性能（但O（1）额外的内存），读每一次转发，最多你到了最后一个之前的节点

例如：

 的IEnumerable< T>反向（节点头）{
堆栈<节点>节点=新的堆栈<节点>（）; 
，而（！头= NULL）{
 nodes.Push（头）; 
 =头head.Next; 
} 
，而（nodes.Count大于0）{
收益率的回报nodes.Pop（）值; 
} 
} 
  

One method which I can think of is to reverse the list and then read it. But this involves changing the list which is bad.
OR I can make a copy of the list and then reverse it, but this uses additional O(n) memory. Is there any better method which doesn't use extra memory and doesn't modify the list and runs in O(n) time

reverse linked list code is something like this in 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;

}

Recursive solution is

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

    Console.WriteLine(n.Data);

}

解决方案

To use O(n) memory and O(n) performance, create a stack; push everything on as you iterate in the forwards direction, then pop everything off, yielding the results.

To use O(n^2) performance (but O(1) extra memory), read it forwards each time, up the the node before the last one you got to.

Example:

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;
    }
}

这篇关于如何向后读取单向链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！