向后打印一个简单的链接列表，没有递归，最多两次，使用恒定的额外内存，保持原样

You must print a simply linked list backwards:

您必须向后打印简单链接列表:

Without recursion
With constant extra memory

随着额外的内存

In linear time

在线性时间

Leaving the list intact

保持列表完好无损

Added Later Two passes at most

最后添加两个传球

6 个解决方案

#1

Building on sharptooth's reply, you can combine the printing and second inversion in the same pass.

在sharptooth的回复基础上,您可以在同一通道中组合打印和第二次反转。

Edit: The "list is left intact" from a single-threaded view because the post-condition equals the pre-condition.

编辑:单个线程视图中的“列表保持不变”,因为后置条件等于前置条件。

Edit 2: Not sure how I got the answer, but I'll take it since I've hit the rep cap for the day. I gave sharptooth a +1 too.

编辑2:不知道我是如何得到答案的,但是我会接受它,因为我已经达到了当天的代表上限。我给了sharptooth一个+1。

#2

Invert the list, print it forwards, invert again. Each step can be done without violating restrictions except the last one.

反转列表,向前打印,再次反转。每个步骤都可以在不违反最后一个限制的情况下完成。

EDIT: As cube notes in the comments the second and the third stages can be combined into one pass. This gives two passes – first reverse, then print while reversing again.

编辑:作为评论中的立方体注释,第二和第三阶段可以组合成一个通道。这给出了两次通过 - 先反转,然后再次反转打印。

#3

Here's a C# implementation that holds for all the current rules. It mutates the list during the execution, but the list is restored before returning.

这是一个C#实现,适用于所有当前规则。它在执行期间改变列表,但在返回之前恢复列表。

using System;
using System.Diagnostics;

namespace SO1135917.Classes
{
    public class ReverseListPrinter
    {
        public static void Execute(Node firstNode, Action<Node> action)
        {
            Reverse(Reverse(firstNode, null), action);
        }

        private static Node Reverse(Node firstNode, Action<Node> action)
        {
            Node node = firstNode;
            Debug.Assert(node != null);

            Node nextNode = node.Next;
            node.Next = null;
            while (node != null)
            {
                if (action != null)
                    action(node);
                if (nextNode == null)
                    break;
                Node nextNode2 = nextNode.Next;

                nextNode.Next = node;
                node = nextNode;
                nextNode = nextNode2;
            }
            return node;
        }
    }
}

There is one problem, however, and that is that the state of the list is undefined if an exception should occur in the above methods. Probably not impossible to handle though.

但是,有一个问题是,如果在上述方法中发生异常,则列表的状态是未定义的。虽然可能并非不可能处理。

A subversion repository of the above code, with unit tests, for Visual Studio 2008 is available here, username and password is both 'guest' without the quotes.

这里提供了上面代码的subversion存储库,带有单元测试,Visual Studio 2008,用户名和密码都是“guest”而没有引号。

#4

You can first check the length of the list. Then create a print-buffer, which you fill in backwards as you traverse the list once again for the information.

您可以先检查列表的长度。然后创建一个打印缓冲区,当您再次遍历列表以获取信息时,将向后填充该缓冲区。

You can create another linked list where you add all the printing data in the front when you traverse the first list, and then print the second list from front to back.

您可以创建另一个链接列表,在遍历第一个列表时在前面添加所有打印数据,然后从前到后打印第二个列表。

Either way makes only two passes at most. The first idea could be done in one pass if you have a header struct that keeps track of the amount of elements in the list.

无论哪种方式最多只能进行两次传球。如果您有一个标题结构来跟踪列表中的元素数量,那么第一个想法可以在一个过程中完成。

Edit: I just realised that these ideas does not use constant memory.

编辑:我刚才意识到这些想法并没有使用恒定的记忆。

The only way to do this sensibly seems to be Sharptooths reply, but that requires three passes.

明智地做到这一点的唯一方法似乎是Sharptooths的回复,但这需要三次通过。

#5

a function like the following might solver your issue:

像下面这样的函数可以解决您的问题:

void invert_print(PtNo l){
  PtNo ptaux = l;
  PtNo last;
  PtNo before;
  while(ptaux != NULL){
    last = ptaux;
    ptaux = ptaux->next;
  }
  while(ptaux != last){
    printf("%s\n", last->info.title);
    ptaux = l;
    before = last;
    while(ptaux != before){
      last = ptaux;
      ptaux = ptaux->next;
    }
  }
}

you will need a structure like the following:

你需要一个像下面这样的结构:

typedef struct InfoNo{
  char title20];
}InfoNo;

typedef struct aPtNo{
  struct InfoNo info;
  struct aPtNo* nextx;
}*PtNo;

#6

Objective-C Link class with reverse method:

Objective-C Link类与反向方法:

Link.h

#import <Foundation/Foundation.h>

@interface Link : NSObject

@property(nonatomic) int value;
@property(nonatomic) Link *next;

- (Link*)reversedList;

@end

Link.m

#import "Link.h"

@implementation Link

- (Link*)reversedList {

    Link* head;

    Link *link = self;
    while (link) {

        // save reference to next link
        Link *next = link.next;

        // "insert" link at the head of the list
        link.next = head;
        head = link;

        // continue processing the rest of the list
        link = next;
    }

    return head;
}

@end

#1