связанный список: Это связанный список, который мы хотим перевернуть.
После обратно связанного списка: Ниже будет результат после обращения вышеприведенного списка.
На приведенной выше примерной диаграмме мы видим, что головной узел и хвостовой узел меняют свое положение, когда мы переворачиваем связанный список. Головной узел, который теперь является хвостовым узлом, указывает на нулевой узел, поскольку теперь он является хвостовым узлом.
Шаги алгоритма
- Мы создаем основной метод и объявляем некоторые необходимые переменные.
- Затем наш следующий шаг — создать метод, который может создать связанный список. Этот метод помогает нам создать связанный список.
- Следующим шагом является создание метода для реверсирования связанного списка. В этом методе мы передаем весь связанный список, и этот метод переворачивает связанный список.
- Теперь нам нужен другой метод для отображения нашего результата после его изменения.
- Мы объединим все эти вышеперечисленные методы в наш основной метод.
Мы собираемся объяснить обратный связанный список, используя некоторую иллюстрированную форму, чтобы облегчить понимание. Итак, начнем с примера.
Ниже приведен связанный список, который мы хотим изменить.
Шаг 1 . Узел зеленого цвета — это головной узел, который указывает на первый узел в запуске.
Шаг 2. На следующем шаге мы пройдем по всему связанному списку, пока не получим нулевой указатель рядом с узлом заголовка. Для этого мы назначим следующему узлу временное имя, как показано на диаграмме ниже.
Шаг 3. Поскольку у нас есть новый ссылочный узел с именем «temporary», который может помочь нам пройти по всему связанному списку до тех пор, пока мы не получим нулевой указатель, мы можем установить следующую ссылку узла заголовка как нулевую, что не повлияет на связанный список, как показано ниже на диаграмме. Нулевой указатель рядом с текущим узлом называется предыдущим узлом.
Шаг 4. Теперь мы перемещаем временный узел на следующий узел, а текущий узел — на предыдущий временный узел. Итак, теперь мы перешли к следующему узлу. Мы также меняем предыдущий узел с нулевого на просто предыдущий узел текущего узла. Итак, теперь временный узел позаботится обо всех обходах до нулевого указателя, чтобы мы могли установить связь текущего узла с предыдущим узлом, и теперь он указывает на предыдущий узел, как показано на диаграмме ниже.
Итак, мы выполняем те же шаги и, наконец, мы получим обратно-связный список.
Шаг 5 .
Шаг 6.
Шаг 7.
Шаг 8.
Шаг 9.
Шаг 10.
Шаг 11.
Шаг 12.
Шаг 13.
Шаг 14. На этом шаге наш связанный список перевернулся.
Программа C++ для обращения связанного списка
#include <иопоток>с использованием пространство имен станд. ;
// Метод для создания узла
структура узел {
инт ценность ;
узел * nextNodePtr ;
} * узелОбъект ;
пустота создать связанный список ( инт н ) ;
пустота реверслинкедлист ( узел ** узелОбъект ) ;
пустота отображать ( ) ;
инт главный ( ) {
инт п,значение,элемент ;
cout << 'Сколько узлов вы хотите создать =>: ' ;
принимать пищу >> н ;
создать связанный список ( н ) ;
cout << ' \n Информация в связанном списке: \n ' ;
отображать ( ) ;
cout << ' \n Связанный список после реверса \n ' ;
реверслинкедлист ( & узелОбъект ) ;
отображать ( ) ;
возвращаться 0 ;
}
// Этот метод создаст связанный список
пустота создать связанный список ( инт н ) {
структура узел * передний узел, * tempNode ;
инт ценность, я ;
узелОбъект знак равно ( структура узел * ) маллок ( размер ( структура узел ) ) ;
если ( узелОбъект == НУЛЕВОЙ )
cout << 'Недостаточно памяти' ;
еще {
cout << 'Пожалуйста, введите информацию об узле 1 (только число):' ;
принимать пищу >> ценность ;
узелОбъект - > ценность знак равно ценность ;
узелОбъект - > nextNodePtr знак равно НУЛЕВОЙ ;
tempNode знак равно узелОбъект ;
за ( я знак равно два ; я <= н ; я ++ ) {
передний узел знак равно ( структура узел * ) маллок ( размер ( структура узел ) ) ;
// Когда нет ни одного узла в связанном списке
если ( передний узел == НУЛЕВОЙ ) {
cout << 'Память не может быть выделена' ;
ломать ;
}
еще {
cout << 'Пожалуйста, введите информацию об узле' << я << ':' ;
принимать пищу >> ценность ;
передний узел - > ценность знак равно ценность ;
передний узел - > nextNodePtr знак равно НУЛЕВОЙ ;
tempNode - > nextNodePtr знак равно передний узел ;
tempNode знак равно tempNode - > nextNodePtr ;
}
}
}
}
пустота реверслинкедлист ( узел ** узелОбъект ) {
структура узел * tempNode знак равно НУЛЕВОЙ ;
структура узел * предыдущий узел знак равно НУЛЕВОЙ ;
структура узел * текущий узел знак равно ( * узелОбъект ) ;
пока ( текущий узел ! знак равно НУЛЕВОЙ ) {
tempNode знак равно текущий узел - > nextNodePtr ;
текущий узел - > nextNodePtr знак равно предыдущий узел ;
предыдущий узел знак равно текущий узел ;
текущий узел знак равно tempNode ;
}
( * узелОбъект ) знак равно предыдущий узел ;
}
пустота отображать ( ) {
структура узел * tempNode ;
если ( узелОбъект == НУЛЕВОЙ ) {
cout << 'Список ссылок пуст' ;
}
еще {
tempNode знак равно узелОбъект ;
пока ( tempNode ! знак равно НУЛЕВОЙ )
{
cout << tempNode - > ценность << ' \т ' ;
tempNode знак равно tempNode - > nextNodePtr ;
}
}
cout << конец ;
}
Выход
Сколько узлов вы хотите создать =>: 6Пожалуйста, введите информацию об узле 1 (только число): 101
Пожалуйста, введите информацию узла 2: 95
Пожалуйста, введите информацию об узле 3: 61
Пожалуйста, введите информацию об узле 4: 19
Пожалуйста, введите информацию об узле 5: 12
Пожалуйста, введите информацию об узле 6: 11
Информация в связанном списке:
101 95 61 19 12 11
Связанный список после реверса
11 12 19 61 95 101
Вывод
В этой статье LinuxHint рассмотрено, как реверсировать связанный список в C++. Есть и другие методы реверсирования связанного списка, но это очень распространенный метод реверсирования связанного списка. Вам решать, как вы хотите решить свои проблемы, но обычно функция обратного связанного списка должна быть простым циклом с перестановкой указателей.