Уплощение двусвязный список


Я на Java dev и пытается подготовиться к интервью на C++. Может кто-то пожалуйста, ознакомьтесь ниже решение для меня?

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

**Я игнорирую, что это двусвязный список на теперь принять разместил код более прост, так как "вдвойне" часть, кажется, не быть любой помощи для меня за этот вопрос.

void LL::flatten(Node *head,Node *tail)
{
    if(!head||!tail) return;

    while(!head->down &&!(head==tail))
    {
        head = head->next;
    }

    // Flattening is complete
    if(head==tail && !head->down) return;



    tail->next = head->down;
    head->down = null;

    //getTail returns the last node of the linkedlist 
    flatten(head->next, getTail(tail->next));        

}


class Node
{
public:
    Node()
    {
        next = prev = down = null;
        data = -1;
    }
private:
    Node * next;
    Node * down;
    Node * prev;
    int data;
};

У меня есть несколько вопросов:

  • Это "вдвойне" обязательной частью. Что я упускаю?
  • Я читал лучше нерекурсивно. Как это? Поскольку у нас есть только указатели на стек и фактических объектов/структура списка в куче, это не должно занять огромное пространство в стеке, кроме обычной рекурсии накладных расходов.
  • У кого-нибудь есть нерекурсивный способ сделать это в C++ или Java. Код на этом форуме в C# и у меня возникли проблемы с пониманием его перечисления и всех итераций
  • В getTail(хвост->следующий) функция \$О(П)\$. Есть ли способ не используя эту функцию ?. Даже если я придаю "вниз" связный список для следующего узла вместо последнего узла, мне понадобится последнего узла "вниз" ЛЛ, так что я могу прикрепить его к следующему узлу родителя.

Хотя я знаю, что там может быть много решение уже опубликовано в другом месте, я ищу обзор на мой код, а также, это поможет мне понять свои пробелы при написании кода в C++ (по крайней мере до интервью стандартам).



Комментарии
2 ответа

Вы могли бы написать этот код в Java во-первых, она не будет сильно отличаться от реализации C++. Похоже, что ваша проблема-это не язык, а алгоритм: например. вы только обновить следующий указатель, а не указатель prev. Следующее должно быть истинным для каждой связи между двумя узлами: узел->далее->пред == узел.

Позвольте мне попытаться ответить на ваши вопросы:


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

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

  • Почему вы хотите нерекурсивный алгоритм? Это не указано в вопросе.

  • Я верю, что вы можете использовать любой язык вам нравится в этом форуме.

4
ответ дан 21 мая 2011 в 07:05 Источник Поделиться

if(!head||!tail) return;

Если это действительно случиться, что голова или хвост может быть null? Это действительно право игнорировать голове ситуации имеет значение null, а хвост нет? Я подозреваю, что этот тест делает.

Не делай этого:

while(!head->down &&!(head==tail))

Сделать это:

while(!head->down && head != tail)

Меньше символов делает его легче читать код.

Что касается алгоритма:

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

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


  1. Guvax guebhtu Н cebprff БС jevgvat Н shapgvba кун sbyybjf ГУР hasynggrarq punva jvgubhg synggravat ВГ. Гура адррес nqq synggravat ГБ Гунг cebprff.

  2. НГ рнпу abqr БЧД ПНА znxr бар БС guerr pubvprf: Zbir Arkg, Zbir Qbja, Zbir Onpx ув.

  3. БЧД Юра zbir qbja, ГУР cerivbhf cbvagre ба ГУР abqr jvyy или hahfrq. ФРГ кун cbvagre ФБ БЧД ПНА pbzr onpx ГБ ГУР cerivbhf yriry.

  4. Zbivat ХК ВФ gevpxl, ОНД БЧД fubhyq xabj ГУР gnvy Анс urnq БС ГУР ybjre yvfg jryy НФ НФ ГУР abqr sebz juvpu БЧД npprffrq ГУР ybjre yvfg. Pnershyyl zbir gubfr cbvagref nebhaq!

1
ответ дан 22 мая 2011 в 09:05 Источник Поделиться