如何向后阅读单链表？

我能想到的一种方法是反转列表然后阅读它。 但这涉及改变不好的清单。
或者我可以复制列表然后反转它，但这会使用额外的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 Reverse (Node head) { Stack nodes = new Stack(); while(head != null) { nodes.Push(head); head = head.Next; } while(nodes.Count > 0) { yield return nodes.Pop().Value; } } 

Answer 2

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

正如前面已经指出的那样; 如果你需要双向遍历列表; 你需要有一个双向链表。 这是双重链表的本质，它是双向的。

Answer 3

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

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

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

Answer 4

如果内存不足，您可以反向列表，迭代它并再次反转。 或者，您可以创建指向节点的堆栈（或者像C＃中的指针一样）。

Answer 5

 void reverse_print(node *head) { node *newHead = NULL, *cur = head; if(!head) return; // Reverse the link list O(n) time O(1) space while(cur){ head = head->next; cur->next = newHead; newHead = cur; cur = head; } // Print the list O(n) time O(1) space cur = newHead; while(cur) { printf(" %d", cur->val); cur = cur->next; } // Reverse the link list again O(n) time O(1) space cur = newHead; while(cur){ newHead = newHead->next; cur->next = head; head = cur; cur = newHead; } // Total complexity O(n) time O(1) space } 

Answer 6

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

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

1. 将列表拆分为两个
2. 递归到列表的后半部分
3. 在中点打印值
4. 进入上半场

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

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

例如，对于百万条目列表，这三个解决方案采用以下顺序：

解决方案内存性能
 =========================================
  Marc＃1 4MB 100万次操作
  矿山80B运营2000万
  Marc＃2 4B 1万亿次运营

Answer 7

假设您的单链表实现IEnumerable ，您可以使用LINQ的反向扩展方法：

 var backwards = singlyLinkedList.Reverse(); 

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

Answer 8

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

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

Answer 9

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

这当然是非常糟糕的表现。

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

伪代码（甚至有bug）：

 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 

Answer 10

这很麻烦，但有效：

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

}

Answer 11

如果在Explicit Stack程序中，我们只为每个节点的数据创建一个堆栈（而不是创建类型堆栈，我们创建类型堆栈）它会不会更好？ 因为我们不需要存储Node的任何其他信息。

 IEnumerable Reverse (Node head) { Stack nodes = new Stack(); while(head != null) { nodes.Push(head.data); head = head.Next; } while(nodes.Count > 0) { yield return nodes.Pop(); } } 

Answer 12

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

Answer 13

出了什么问题：

  public void printBackwards(LinkedList sl){ ListIterator litr = sl.listIterator(sl.size()); Element temp; while(litr.previousIndex() >= 0){ temp = litr.previous(); System.out.println(temp); } } 

O（n）性能，O（1）记忆和简单的do-re-mi！