Напечатайте просто связанный список в обратном направлении без рекурсии, максимум за два прохода, используя постоянную дополнительную память, оставляя ее нетронутой

Question

Вы должны напечатать просто связанный список в обратном направлении:

• без рекурсии
• С постоянной дополнительной памятью
• В линейное время
• Оставление списка без изменений
• Добавлено позже Максимум два прохода

Answer 1

Инвертировать список, распечатать его вперед, инвертировать снова. Каждый шаг может быть выполнен без нарушения ограничений, кроме последнего.

РЕДАКТИРОВАТЬ: Как куб отмечает в комментариях, второй и третий этапы могут быть объединены в один проход. Это дает два прохода - сначала задний ход, затем печать при повторном обращении.

Answer 2

Опираясь на ответ Sharp, вы можете объединить печать и вторую инверсию за один проход.

Редактировать: «список остался нетронутым» из однопоточного представления, потому что постусловие равно предварительному условию.

Редактировать 2: Не уверен, как я получил ответ, но я возьму его, так как я достиг предела репутации за день. Я тоже дал острый зуб +1.

Answer 3

Вот реализация 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 здесь , имя пользователя и пароль - «гость» без кавычек.

Answer 4

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

Answer 5

функция, подобная следующей, может решить вашу проблему:

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;

Answer 6

Вы можете сначала проверить длину списка. Затем создайте буфер печати, который вы заполняете задом наперед при повторном просмотре списка для получения информации.

или

Вы можете создать еще один связанный список, в который вы добавляете все данные печати спереди при прохождении первого списка, а затем печатаете второй список спереди назад.

В любом случае можно сделать только два прохода. Первая идея может быть реализована за один проход, если у вас есть структура заголовка, которая отслеживает количество элементов в списке.

Редактировать: я только что понял, что эти идеи не используют постоянную память.

Единственный способ сделать это разумно - это ответ Sharptooths, но для этого нужно три прохода.