Учитывая head
односвязного списка, переверните список и верните обратный список.
Пример 1:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Решение:
В данной задаче мы должны перевернуть связанный список, и после обращения мы должны вернуть перевернутый связанный список.
Инвертирование связанного списка означает, что первый узел связанного списка становится последним узлом, а последний узел становится первым узлом списка.
Поэтому для обращения связанного списка мы создадим три указателя, prev, cur и n, для хранения предыдущего, текущего и следующий узел соответственно.
ListNode* prev = NULL; ListNode* cur = head; ListNode* n;
Следующим шагом будет обход списка до тех пор, пока указатель cur не станет нулевым.
Пока указатель cur не равен null, указатель n будет указывать на следующий из узлов cur и указатель next of cur становится указателем prev. Тогда указатель prev станет указателем cur, а cur станет указателем n. Таким образом, узлы меняются местами.
while(cur != NULL){ n = cur -> next; cur -> next = prev; prev = cur; cur = n; }
Теперь последний шаг — вернуть указатель prev, чтобы получить перевернутый связанный список.
return prev;
Ниже приведена полная реализация задачи:
Спасибо за прочтение!
S.