1

您必须向后打印一个简单的链表：

  • 没有递归
  • 具有恒定的额外内存
  • 在线性时间内
  • 保持列表不变
  • 后加 最多两遍
4

6 回答 6

10

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

编辑：正如评论中的立方体注释，第二和第三阶段可以合并为一次。这给出了两次通过 - 第一次反转，然后在再次反转时打印。

于 2009-07-16T07:20:37.247 回答
3

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

编辑：来自单线程视图的“列表保持不变”，因为后置条件等于前置条件。

编辑 2：不知道我是如何得到答案的，但我会接受它，因为我已经达到了当天的代表上限。我也给了锐齿+1。

于 2009-07-16T07:30:04.373 回答
1

这是适用于所有当前规则的 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;
        }
    }
}

然而，有一个问题，那就是如果在上述方法中发生异常，则列表的状态是未定义的。可能不是不可能处理。

上述代码的 subversion 存储库，带有单元测试，用于 Visual Studio 2008 可在此处获得，用户名和密码都是不带引号的“guest”。

于 2009-07-20T11:30:43.457 回答
0

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

或者

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

无论哪种方式，最多只能通过两次。如果您有一个跟踪列表中元素数量的标头结构，则可以一次性完成第一个想法。

编辑：我刚刚意识到这些想法不使用常量内存。

明智地做到这一点的唯一方法似乎是Sharptooths回复，但这需要三遍。

于 2009-07-16T07:36:30.977 回答
0

类似以下的功能可能会解决您的问题：

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

您将需要如下结构：

typedef struct InfoNo{
  char title20];
}InfoNo;

typedef struct aPtNo{
  struct InfoNo info;
  struct aPtNo* nextx;
}*PtNo;
于 2009-09-10T04:32:06.903 回答
0

具有反向方法的 Objective-C 链接类：

链接.h

#import <Foundation/Foundation.h>

@interface Link : NSObject

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

- (Link*)reversedList;

@end

链接.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
于 2014-11-02T01:02:54.110 回答