Рекурсивно развернуть односвязный список

@fears · Регистрация: 18.11.2018

Студворк — интернет-сервис помощи студентам

Пытаюсь разобраться в какой момент происходит разворачивание списка и как
1->2->3->4->5->nullptr

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
 
class Solution {
public:
    ListNode* reverseList(ListNode* head) {  [B]тут все ясно,передаем "1" - head проверяем пуст ли, или один элемент в списке[/B]
          if(head == nullptr || head->next == nullptr){
                return head;
          }
          ListNode* ans = reverseList(head->next) [B]тут я не уверен, мы создаем указатель на "2"[/B]
          head->next->next=head; [B]1->2->1 затираем указатель и получаем 2->1[/B]
          head->next = nullptr; [B]дальше делаем 1->nullptr[/B]
          return head;
    }
};

Можно пояснить, как для чайника, где рекурсивная функция и где переворачивается лист и как, а то, что-то сам не смогу разобраться

@SmallEvil · 08.03.2023, 15:29

Сообщение от fears

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

Он не выполняет поставленной задачи. Зачем разбираться в нерабочем коде ?

Добавлено через 25 минут
return head;
return ans;

@fears · 08.03.2023, 15:58 **[ТС]**

на leetcode проходит, ну и решение от призера мира по программированию.

Добавлено через 8 минут

Сообщение от SmallEvil

return head;
return ans;

Да и это я накосячил, должен быть ans

@SmallEvil · 08.03.2023, 16:11

Сообщение от fears

Да и это я накосячил

молодец

Что бы понять как это работает, нужно и рассматривать снизу-вверх, так же как и построена рекурсия.
15 - 17 строки
в них вы попадете только и только когда в списке присутствует как минимум два узла.
Теперь начинайте представлять с конца список, так как в конце рекурсии ans будет указывать на последний узел.
1->2->3->4->5 /->nullptr/
Конец отбрасываем, мы до него не дойдем.
-> обозначает "указывает"
head -> '5' - return head // next -> nullptr
вышли из рекурсии, подымаемся вверх
ans -> 5
head -> 4
head->next->next = head(4) // развернули связь
head->next = nullptr; // поставили заглушку, на случай если элемент последний (первый)
возвращаем указатель на хвост, всегда на хвост.

@fears · 08.03.2023, 16:17 **[ТС]**

спасибо большое !!!!!!!!!!!!!!!! очень помогли и нормально пояснили, спасибо!!!!

@SmallEvil · 08.03.2023, 16:20

Сообщение от fears

ListNode* reverseList(ListNode* head)

название переменно head дико жуткое, и не отражает смысла её назначения, это просто узел.

Добавлено через 2 минуты

Сообщение от SmallEvil

возвращаем указатель на хвост, всегда на хвост.

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

@vlisp · 08.03.2023, 17:52

Это где ж это научились гнуть спину, разворачиванием списков? Это же какое-сумасшествие или невежество.списки предназначены для 2 операций — пуш и поп, которые они делают за О(1). Реверс списка — это О(и) операций, что уже не достойно внимания. Тем более код на 3-4с строки—нужно отпушить из одной головы в другую. В си список состоит из одного класса. В плюсах — из 2х: нод и собственно список сверху. Тут же какой-то класс непонятный типа учебный?

@SmallEvil · 08.03.2023, 17:59

Сообщение от vlisp

Тут же какой-то класс непонятный типа учебный?

Это просто задачки.
Что бы сделать, не больше.

Добавлено через 3 минуты

Сообщение от vlisp

Реверс списка — это О(и) операций

Кроме операций еще и по памяти займет (указатель head + указатель ans) * N
Плюс при длинном списке переполнится стек.
Рассматривать его с практической точки не имеет никакого смысла.

Новые блоги и статьи Все статьи Все блоги /
10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .
Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .

@fears 0 / 0 / 0 Регистрация: 18.11.2018 Сообщений: 45
	08.03.2023, 16:17 [ТС]
	спасибо большое !!!!!!!!!!!!!!!! очень помогли и нормально пояснили, спасибо!!!! 0

@vlisp 1064 / 985 / 153 Регистрация: 10.08.2015 Сообщений: 5,385
	08.03.2023, 17:52
	Это где ж это научились гнуть спину, разворачиванием списков? Это же какое-сумасшествие или невежество.списки предназначены для 2 операций — пуш и поп, которые они делают за О(1). Реверс списка — это О(и) операций, что уже не достойно внимания. Тем более код на 3-4с строки—нужно отпушить из одной головы в другую. В си список состоит из одного класса. В плюсах — из 2х: нод и собственно список сверху. Тут же какой-то класс непонятный типа учебный? 0

Рекурсивно развернуть односвязный список

Решение