Реверсирование списка ссылок с использованием итеративного подхода

Что не так с моим кодом для обращения связанного списка?

void rev(node* &head)
{
    int flag=0;
    node* head1=NULL;
    while(head->next!=NULL)
    {
        node* temp1=head;
        node* temp2=head;
        while(temp1->next!=NULL)
        {
            temp2=temp1;
            temp1=temp1->next;
        }
        if (flag==0)
        {
            head1=temp1;
            flag++;
        }
        temp1->next=temp2;
        temp2->next=NULL;
    }
    head=head1;
    delete head1;
}

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

Он не компилируется. Он неполный godbolt.org/z/n8f1faoPj

463035818_is_not_a_number 10.01.2023 14:45

Две вещи, вы нарисовали на листе бумаги, что происходит со всеми указателями? И, во-вторых, пробовали ли вы запустить свой код в отладчике и убедиться, что каждый шаг (переназначение указателя) происходит так же, как вы нарисовали на бумаге? (Также обратите внимание, что односвязные списки не очень хороши для реверсирования, если вам это нужно часто, используйте двусвязный список).

Pepijn Kramer 10.01.2023 14:46

Я не понимаю код, но последние две строки особенно удивительны. head=head1; delete head1; head — это то, что вы изменяете, потому что вызывающий абонент передал его вам. Почему вы удаляете узел, на который он указывает?

463035818_is_not_a_number 10.01.2023 14:46

«стандартный» способ перевернуть связанный список в C++ — это std::list::reverse.

463035818_is_not_a_number 10.01.2023 14:48

Еще одна проблема, которую я вижу, заключается в том, что reverse не является функцией-членом класса списка. Тогда вам не нужно отдельно передавать указатель на голову, и вы можете проверить, пуст ли список или нет.

Pepijn Kramer 10.01.2023 14:48

Считаете ли вы, что в рамках вашей цели «обратить список ссылок» необходимо delete какой-то случайный существующий узел в списке? Если да, то почему? Если нет, то чего именно вы ожидаете от этого оператора delete в конце функции?

Sam Varshavchik 10.01.2023 14:49

@ 463035818_is_not_a_number Что ж, стандартным способом действительно было бы НЕ писать свой собственный список. Но я предполагаю, что это для класса структур данных (что не то же самое, что изучение правильного С++)

Pepijn Kramer 10.01.2023 14:49

@PepijnKramer действительно. Я всегда немного смущаюсь, когда они предполагают, что реализация связанного списка очевидна. Я так не думаю. Я думаю, что детали имеют значение. И поскольку они также, кажется, предполагают, что очевидно, что в С++ связанный список является самозаписываемым, почему бы не указать им правильный;)

463035818_is_not_a_number 10.01.2023 14:55

Нарисовав это на бумаге, решение было бы найдено довольно быстро. Все, что вам нужно сделать, чтобы перевернуть (односвязный) список, это переместить стрелки в другую сторону, а затем переместить указатель головы. И я тоже не шучу. Это буквально алгоритм.

sweenish 10.01.2023 15:05

FWIW, я не согласен с аргументацией близких голосов. Во всяком случае, это будет проблема «деталей или ясности». Но я считаю, что кода/информации достаточно, чтобы дать ответ на заданный вопрос, поэтому я проголосовал за повторное открытие.

sweenish 10.01.2023 15:11

Проблема, по-видимому, заключается в том, что вы проходите весь список на каждой (внешней) итерации и, кажется, просто навсегда меняете местами последние два элемента. Вы никогда не обновляете head, поэтому самый внешний цикл бесконечен. Вам нужно менять указатели по мере прохождения, и вы, естественно, будете знать, где переназначить head, когда дойдете до конца; нет необходимости в специальной проверке. Это операция O(n), и вы сделали ее нефункциональной O(n^2).

sweenish 10.01.2023 15:15

@Charlie Я подготовил демонстрационную программу, которая показывает, как можно обратить односвязный список, но, к сожалению, ваш вопрос уже закрыт. :)

Vlad from Moscow 10.01.2023 15:41
Калькулятор CGPA 12 для семестра
Калькулятор CGPA 12 для семестра
Чтобы запустить этот код и рассчитать CGPA, необходимо сохранить код как HTML-файл, а затем открыть его в веб-браузере. Для этого выполните следующие...
Как собрать/развернуть часть вашего приложения Angular
Как собрать/развернуть часть вашего приложения Angular
Вам когда-нибудь требовалось собрать/развернуть только часть вашего приложения Angular или, возможно, скрыть некоторые маршруты в определенных средах?
Запуск PHP на IIS без использования программы установки веб-платформы
Запуск PHP на IIS без использования программы установки веб-платформы
Установщик веб-платформы, предлагаемый компанией Microsoft, перестанет работать 31 декабря 2022 года. Его закрытие привело к тому, что мы не можем...
Оптимизация React Context шаг за шагом в 4 примерах
Оптимизация React Context шаг за шагом в 4 примерах
При использовании компонентов React в сочетании с Context вы можете оптимизировать рендеринг, обернув ваш компонент React в React.memo сразу после...
Библиотека для работы с мороженым
Библиотека для работы с мороженым
Лично я попрощался с операторами print() в python. Без шуток.
Настройка шаблона Metronic с помощью Webpack и Gulp
Настройка шаблона Metronic с помощью Webpack и Gulp
Я пишу эту статью, чтобы поделиться тем, как настроить макет Metronic с помощью Sass, поскольку Metronic предоставляет так много документации, и они...
2
12
78
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Ваша функция недействительна.

Например, переданный указатель head может быть равен nullptr. В этом случае это цикл while

while(head->next!=NULL)

Уже может вызывать неопределенное поведение.

Или в списке нечего удалять, но в функции есть эти операторы

head=head1;
delete head1;

Это не имеет смысла.

Даже если убрать оператор с вызовом delete, все равно это не делает функцию корректной. Например, если список содержит только один узел, то этот цикл while

while(head->next!=NULL)

Выполняться не будет. В результате указатель head будет установлен на NULL из-за этого оператора после цикла

head=head1;

Потому что перед циклом указатель head1 установлен на NULL

node* head1=NULL;

Также кажется, что в этом вложенном цикле while

while(temp1->next!=NULL)
{
    temp2=temp1;
    temp1=temp1->next;
}

Вы пытаетесь найти последний узел в списке, который как минимум неэффективен.

А ваша функция неясна и слишком сложна.

Для написания функции достаточно выучить стандартную функцию C++ std::exchange, объявленную в заголовке <functional>, что сделает код функции более простым и понятным.

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

#include <iostream>
#include <functional>
#include <iterator>

struct node
{
    int data;
    node *next;
};

void clear( node * &head )
{
    while ( head ) delete std::exchange( head, head->next );
}

void assign( node * &head, const int a[], size_t n )
{
    clear( head );

    for (node **current = &head; n--; current = &( *current )->next)
    {
        *current = new node{ *a++, nullptr };
    }
}

std::ostream & display( const node *const &head, std::ostream &os = std::cout )
{
    for (const node *current = head; current != nullptr; current = current->next)
    {
        os << current->data << " -> ";
    }

    return os << "null";
}

void reverse( node * &head )
{
    for ( node *current = head, *previous = nullptr; current != nullptr; previous = head )
    {
        head = std::exchange( current, current->next );
        head->next = previous;
    }
}

int main()
{
    node *head = nullptr;
    const int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    assign( head, a, std::size( a ) );

    display( head ) << '\n';

    reverse( head );

    display( head ) << '\n';

    clear( head );
}

Вывод программы

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null

Как видите, функция имеет только один цикл for, составной оператор которого содержит только два оператора.

void reverse( node * &head )
{
    for ( node *current = head, *previous = nullptr; current != nullptr; previous = head )
    {
        head = std::exchange( current, current->next );
        head->next = previous;
    }
}

Без использования стандартной функции std::exchange функция, переворачивающая список, будет иметь еще один оператор, например

void reverse( node * &head )
{
    for ( node *current = head, *previous = nullptr; current != nullptr; previous = head )
    {
        head = current;
        current = current->next; 
        head->next = previous;
    }
}

@Чарли Спасибо. Я уже проголосовал за ваш вопрос. :)

Vlad from Moscow 10.01.2023 18:33

Во-первых, мини-обзор кода:

//
// Bigger issues implied by this function are that it is not a very good
// linked list, likely an extremely basic C-style list. However, that is
// beyond the scope of this question.
//
void rev(node* &head)
{
    int flag=0;  // Unnecessary
    node* head1=NULL;  // Prefer nullptr
    while(head->next!=NULL)
    {
        node* temp1=head;
        node* temp2=head;  // Choose better names
        while(temp1->next!=NULL)  // Traverse the entire list at every iteration
        {
            temp2=temp1;
            temp1=temp1->next;
        }
        if (flag==0)
        {
            head1=temp1;
            flag++;
        }
        temp1->next=temp2;  // Always and only swaps the last two elements
        temp2->next=NULL;

        // Never updates head in the loop; loop is infinite
    }
    head=head1;
    delete head1;  // head1 was pointing to a valid node; you just nuked your
                   // entire list
}

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

Специальный чек head и flag не нужны. Вы, естественно, доберетесь до хвоста и сможете переназначить голову, когда сделаете это.

Вот переработанный алгоритм:

#include <iostream>

struct node {
  int data;
  node* next;

  node(int d) : data(d), next(nullptr) {}
};

//
// Bigger issues implied by this function is that it is not a very good
// linked list, likely an extremely basic C-style list. However, that is
// beyond the scope of this question.
//
void rev(node*& head) {
  node* prev = nullptr;
  node* curr = head;
  node* next = nullptr;  // Not immediately assigned to account for
                         // empty list.

  while (curr) {
    next = curr->next;  //
    curr->next = prev;  // This order of operations is very important
    prev = curr;        //
    curr = next;        //
  }

  head = prev;
}

int main() {
  node* list = new node{1};
  list->next = new node{2};
  list->next->next = new node{3};
  list->next->next->next = new node{4};
  list->next->next->next->next = new node{5};

  node* walker = list;
  std::cout << "Original list: ";
  while (walker != nullptr) {
    std::cout << walker->data << ' ';
    walker = walker->next;
  }
  std::cout << '\n';

  rev(list);
  std::cout << "Reversed list: ";
  walker = list;
  while (walker != nullptr) {
    std::cout << walker->data << ' ';
    walker = walker->next;
  }
  std::cout << '\n';

  // On the one hand, I don't delete my nodes. On the other,
  // the program is ending and the OS will clean up my mess.
  // This is generally a bad practice.
}

Выход:

❯ ./a.out
Original list: 1 2 3 4 5 
Reversed list: 5 4 3 2 1 

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

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

Другие вопросы по теме