Блог

У меня есть код решения здесь:

 // Pre-condition: The fronts of two linked lists are provided.
// Post-condition: A linked list is returned that is the result of
// interleaving the elements from each provided list. 
// (e.g. {1, 2, 3} amp; { 4, 5, 6} would return {1, 4, 2, 5, 3, 6}

Node* interleave( Node*amp; front1, Node*amp; front2 ) {
    if( !front1 ) return front2;
    if( !front2 ) return front1;

    Node* third = front1->next; //this will become the third element
    Node* fourth = front2->next; // this will be come the fourth element

    front1->next = front2;
    front2->next = third;

    third = interleave(third, fourth);

    return front1;  
}
  

Я вроде как понимаю это, но я бы никогда не смог придумать что-то подобное, поскольку я очень плох в рекурсии. Есть ли другой способ решить эту проблему нерекурсивно? если да, не могли бы вы дать мне подсказку? Я пробовал это:

 Node* interleave( Node*amp; front1, Node*amp; front2 ) {
    Node* newNode = new Node;
    while(front1!=NULL amp;amp; front2!=NULL){
        newNode = front1->next;
        newNode = front2->next;
        front1 = front1->next;
        front2 = front2->next;
     }
    return newNode;
}
  

Я уверен, что это неправильно, но это единственное, что я могу придумать прямо сейчас. Пожалуйста, помогите. Спасибо

Попробуйте нарисовать два связанных списка параллельно на листе бумаги. Поместите несколько чисел в узлы, просто чтобы отличить их друг от друга. Подумайте, как бы вы повторно соединили их, чтобы сформировать единый список, начиная с заголовка (или «начала») и продвигаясь вниз. Обратите внимание, что вам нужно отслеживать несколько специальных узлов, таких как первый узел результирующего списка и несколько других. Шаблон должен стать понятным.

(Обратите внимание, что нет необходимости создавать новый узел с new .)

В вашем коде есть несколько ошибок:

 Node* interleave( Node*amp; front1, Node*amp; front2 )
  

Я не вижу необходимости в ссылке на указатель, поскольку первый элемент в front1 будет оставаться первым, и вам вообще не нужно связываться с front2.

 Node* newNode = new Node;
while(front1!=NULL amp;amp; front2!=NULL){
    newNode = front1->next;
  

Это вызывает утечку памяти — вы выделяете по крайней мере байты sizeof (узла), но затем вы теряете ссылку на указатель, и вы больше не сможете его удалить.
Кроме того, вы ничего не делаете с newNode, поэтому вы также можете выбросить его.

 front1 = front1->next;
front2 = front2->next;
  

По сути, вы говорите, что front1 скорее будет указывать на следующий элемент, и поскольку вы передали ссылку на front1, вы изменяете реальный указатель. В конечном итоге front1 или front2 будут равны НУЛЮ, и цикл завершится, так что по крайней мере один из двух заданных параметров станет бесполезным. Далее вы ничего не меняете, поэтому порядок останется неизменным — вы просто проходите по спискам.

Одним из подходов могло бы быть присвоение значению front2 значения front1-> next, затем замена указателей и повторение снова:

 Node *a = front1, *b = front2;
while (a amp;amp; b) {
    Node* tmp = a->next;
    a->next = b;
    b = tmp;
    a = a->next;
}
return front1;
  

Я не тестировал это, но это должно быть близко к работе. Вы можете заменить подробный код подкачки на std::swap(), если вы используете stl.
Идея проста: предположим, у вас есть два списка:

A -> B -> C -> NULL
D -> E -> F -> NULL

вы говорите, что следующий элемент A будет первым элементом во втором списке, поэтому D:

A -> D -> E -> F -> NULL

и тогда второй список становится преемником древнего A, так что просто B -> C -> NULL. Затем вы продвигаете a, чтобы указать на его новый следующий, или D, так что теперь у вас есть:

D -> E -> F -> NULL
B -> C -> NULL

и вы повторяете:

D -> B -> C -> NULL
E -> F -> NULL

B -> C -> NULL
F -> NULL

и так далее, пока не будет выполнено значение NULL. Тогда front1, который все еще указывает на A, должен иметь правильную последовательность (то есть, если я не ужасно ошибаюсь : p )