Вам дан связанный список. Напишите функцию, чтобы обратить его.

Пример:

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

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

Наблюдать

Связанный список можно разделить на головной узел и хвост, который также является связанным списком, но возглавляется вторым узлом.

Советы:
трактуйте хвост как связанный список и реверсируйте его, рекурсивно вызывая функцию реверса.

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

Алгоритм

  1. Покройте крайние случаи нулевого и одноэлементного связанного списка.
  2. Получите второй узел из исходного связанного списка и рекурсивно переверните хвост.
  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).