C# 如何向后读取单向链表？

How to read a singly linked list backwards?

提问by Learner

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

我能想到的一种方法是反转列表然后读取它。但这涉及更改不好的列表。
或者我可以复制列表然后反转它，但这会使用额外的 O(n) 内存。有没有更好的方法不使用额外的内存并且不修改列表并在 O(n) 时间内运行

reverse linked list code is something like this in c#

反向链表代码在 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);

}

采纳答案by Marc Gravell

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.

要使用 O(n) 内存和 O(n) 性能，请创建一个堆栈；在向前迭代时推动所有内容，然后弹出所有内容，产生结果。

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.

要使用 O(n^2) 性能（但 O(1) 额外内存），请每次向前读取它，在最后一个节点之前向上读取。

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

回答by Lasse V. Karlsen

Well, the naive solution would be to keep track of which node you're currently at, then iterate from the start until you find that node, always saving the node you just left. Then each time you find the node you're currently at, you produce the node you just left, save that node as the one you're currently at, then re-iterate from the start.

好吧，天真的解决方案是跟踪您当前所在的节点，然后从头开始迭代，直到找到该节点，始终保存您刚刚离开的节点。然后每次找到当前所在的节点时，都会生成刚刚离开的节点，将该节点保存为当前所在的节点，然后从头开始重新迭代。

This would of course be horribly bad performance-wise.

这当然会在性能方面非常糟糕。

I'm sure some smarter people have a better solution.

我相信一些更聪明的人有更好的解决方案。

Pseudo-code (with bugs even):

伪代码（甚至有错误）：

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

回答by cube

you could read it in O(n^2) -- every time go to the last node read and print out the previous one

你可以在 O(n^2) 中读取它——每次去最后一个节点读取并打印出前一个

回答by sanity

Really you should be using a doubly-linked list.

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

If this isn't possible, I think your best option will be to construct a copy of the list that has been reversed.

如果这是不可能的，我认为您最好的选择是构建已反转列表的副本。

Other options, such as relying on recursion (effectively copying the list to the stack) could cause you to run out of stack space if the list is too long.

如果列表太长，其他选项，例如依赖递归（有效地将列表复制到堆栈）可能会导致您用完堆栈空间。

回答by user131314

If you short of memory you can reverse list, iterate over it and reverse it again. Alternatively you can make a stack of pointers to nodes (or whatever is like a pointer in C#).

如果您的内存不足，您可以反转列表，迭代它并再次反转它。或者，您可以制作一堆指向节点的指针（或任何类似于 C# 中的指针）。

回答by Williham Totland

One of the hallmarks of a singly-linked list is that it is, in fact, singly linked. It is a one-way street, and there's no way to overcome that unless you turn it into something else (such as a reversed singly-linked list, a stack, a doubly-linked list...). One must be true to the nature of things.

单向链表的标志之一是它实际上是单向链接的。这是一条单向的街道，除非你把它变成别的东西（比如反向单链表、堆栈、双链表……），否则没有办法克服它。一个人必须忠于事物的本质。

As has been pointed out earlier; if you need to traverse a list both ways; you need to have a doubly-linked list. That is the nature of a doubly linked list, it goes both ways.

正如前面所指出的；如果您需要双向遍历列表；你需要有一个双向链表。这就是双向链表的本质，它是双向的。

回答by sillydino

This is messy but works:

这很乱，但有效：

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

}

}

回答by Judah Gabriel Himango

Assuming your singly-linked list implements IEnumerable<T>, you can utilize LINQ's Reverse extension method:

假设您的单链表实现了 IEnumerable<T>，您可以利用 LINQ 的反向扩展方法：

var backwards = singlyLinkedList.Reverse();

You'll need to add a using System.Linq;directive at the top of the code file to use LINQ's extension methods.

您需要using System.Linq;在代码文件的顶部添加一个指令才能使用 LINQ 的扩展方法。

回答by Motti

A variation of creating a stack and pushing all the elements onto the stack is to use recursion (and the system's built in stack), this is probably not the way to go with production code but serves as a better (IMHO) interview answer for the following reasons:

创建堆栈并将所有元素推送到堆栈上的一种变体是使用递归（和系统的内置堆栈），这可能不是生产代码的方法，但可以作为更好的（恕我直言）面试答案以下原因：

1. It shows that you grok recursion
2. It's less code and appears more elegant
3. A naive interviewer may not realize that there is a space overhead (if this is the case you may want to consider whether you want to work there).

1. 它表明你熟悉递归
2. 它的代码更少，看起来更优雅
3. 天真的面试官可能没有意识到空间开销（如果是这种情况，您可能需要考虑是否要在那里工作）。

回答by Alice Purcell

There is a third solution, this time using O(log(n))memory and O(n log(n))time, thus occupying the middle ground between the two solutions in Marc's answer.

还有第三种解决方案，这次使用O(log(n))内存和O(n log(n))时间，因此在 Marc 的答案中占据了两种解决方案之间的中间地带。

It is effectively a reverse in-order descent of a binary tree [O(log(n))], except at each step you need to find the top of the tree [O(n)]:

它实际上是二叉树 [ O(log(n))]的逆序下降，除了在每一步都需要找到树 [ O(n)]的顶部：

1. Split the list in two
2. Recurse into the second half of the list
3. Print the value at the midpoint
4. Recurse into the first half

1. 将列表一分为二
2. 递归到列表的后半部分
3. 打印中点的值
4. 回归上半场

Here is the solution in Python (I don't know C#):

这是 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)

This could be recast using iteration instead of recursion, but at the cost of clarity.

这可以使用迭代而不是递归来重铸，但要以清晰为代价。

For example, for a million-entry list, the three solutions take on the order of:

例如，对于百万条目列表，三种解决方案的顺序为：

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