Сложность: easy
Дан односвязный список, разверните этот список и верните развернутый список.
Пример:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
👨💻 Алгоритм:
1⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.
2⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.
3⃣После завершения цикла верните prev как новую голову развернутого списка.
😎 Решение:
class ListNode {
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class Solution {
function reverseList($head) {
$prev = null;
$curr = $head;
while ($curr !== null) {
$nextTemp = $curr->next;
$curr->next = $prev;
$prev = $curr;
$curr = $nextTemp;
}
return $prev;
}
}Ставь 👍 и забирай 📚 Базу знаний