如何向后读取单链表？

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(log(n)) 内存和 O(n log(n)) 时间，从而占据两者之间的中间立场马克的回答中的解决方案。

它实际上是二叉树的逆序下降 [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)

这可以重新转换使用迭代而不是递归，但以清晰度为代价。

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

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

Answer 2

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 3

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

var backwards = singlyLinkedList.Reverse();

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

Answer 4

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

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

Answer 5

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

这当然会导致性能非常糟糕。

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

伪代码（甚至有错误）：

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 6

这很混乱但有效：

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 7

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

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

Answer 8

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

Answer 9

有什么问题：

    public void printBackwards(LinkedList sl){    
        ListIterator<Element> 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！

Answer 10

要使用 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 11

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

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

Answer 12

实际上你应该使用双向链表。

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

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

Answer 13

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