Вам дан связанный список. Напишите функцию, чтобы обратить его.
Пример:
The original linked list is as follows: 3 -> 5 -> 2 -> 4
The reversed linked list has its arrows changed in direction: 3 <- 5 <- 2 <- 4
which means 4 -> 2 -> 5 -> 3
Не создавайте новые узлы. Вместо этого повторно используйте исходный связанный список и измените направления стрелок на месте.
Входные данные:
значения узлов связанного списка, разделенные запятыми.
3 5 2 4
Вывод:
значения узла перевернутого связанного списка, разделенные запятыми.
4 2 5 3
Решение: реверсировать связанный список
Наблюдать
Связанный список можно разделить на головной узел и хвост, который также является связанным списком, но возглавляется вторым узлом.
Советы:
трактуйте хвост как связанный список и реверсируйте его, рекурсивно вызывая функцию реверса.
Затем первый узел добавляется к перевернутому хвосту, чтобы построить весь перевернутый связанный список.
Алгоритм
- Покройте крайние случаи нулевого и одноэлементного связанного списка.
- Получите второй узел из исходного связанного списка и рекурсивно переверните хвост.
- Добавьте первый узел в конец перевернутого хвоста.
Код
/** * class Node { * val: number, * next: Node, * } */
/** * @param {Node} head Head of the linked list. * @return {Node} Head of the reversed linked list. */ function reverseLinkedList(head) { if (head == null || head.next == null) { return head; }
const secondNode = head.next; const reversedTail = reverseLinkedList(secondNode); secondNode.next = head; head.next = null;
return reversedTail; }
Анализ сложности
Пусть N будет длиной связанного списка.
Мы посещаем каждый узел в связанном списке один раз, поэтому общая сложность составляет O(N).