如何向后阅读单链表？

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

}

13 个解决方案

#1

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

#2

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.

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

#3

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.

其他选项,例如依赖递归(有效地将列表复制到堆栈)可能会导致如果列表太长则耗尽堆栈空间。

#4

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#中的指针一样)。

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

#6

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)]:

Split the list in two

将列表拆分为两个

Recurse into the second half of the list

递归到列表的后半部分

Print the value at the midpoint

在中点打印值

Recurse into the first half

进入上半场

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

#7

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

假设您的单链表实现IEnumerable ,您可以使用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.

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

#8

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:

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

It shows that you grok recursion

它显示你grok递归

It's less code and appears more elegant

它的代码更少,看起来更优雅

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).

一个天真的面试官可能没有意识到存在空间开销(如果是这种情况,你可能想要考虑是否要在那里工作)。

#9

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

#10

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

}

#11

If in the Explicit Stack program, we create a stack for just the data of each node (instead of creating the Stack of type <Node>, we create Stack of type <T>) wouldn't it be even better? Because we don't need to store any other information of the Node then.

如果在Explicit Stack程序中,我们只为每个节点的数据创建一个堆栈(而不是创建类型为的堆栈,我们创建类型的堆栈)会不会更好?因为我们不需要存储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();
    }
}

#12

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)中读取它 - 每次去最后一个节点读取并打印出前一个节点

#13

What's wrong with:

有什么不对:

    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) performance, O(1) memory and simple as do-re-mi!

O(n)性能,O(1)记忆和简单的do-re-mi!

#1