c# - 如何向后读取单向链表？

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