206. Reverse Linked List

Задача

Дан односвязный список. Необходимо развернуть его в обратном порядке и вернуть новую голову списка.

// Структура узла
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}
 
// Способ 1: Создание вручную
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

// Структура узла двусвязного списка
function DoublyListNode(val, prev, next) {
    this.val = (val === undefined ? 0 : val);
    this.prev = (prev === undefined ? null : prev);
    this.next = (next === undefined ? null : next);
}

Примеры

Пример 1

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Пример 2

Input: head = [1,2]
Output: [2,1]

Пример 3

Input: head = []
Output: []

Решение

Решение

// Временная сложность: O(n)
// Пространственная сложность: O(1)
 
function reverseList(head) {
    let prev = null;
    let current = head;
 
    while (current !== null) {
        // Сохраняем следующий узел
        let next = current.next;
 
        // Разворачиваем указатель
        current.next = prev;
 
        // Двигаем указатели вперед
        prev = current;
        current = next;
    }
 
    // prev теперь указывает на новую голову
    return prev;
}

Решение

// Временная сложность: O(n)
// Пространственная сложность: O(1)
 
function reverseDoublyList(head) {
    let temp = null;
    let current = head;
 
    // Проходим по всем узлам и меняем местами prev и next
    while (current !== null) {
        // Сохраняем prev во временную переменную
        temp = current.prev;
 
        // Меняем местами prev и next
        current.prev = current.next;
        current.next = temp;
 
        // Переходим к следующему узлу (который теперь в prev)
        current = current.prev;
    }
 
    // temp.prev указывает на новую голову (бывший хвост)
    if (temp !== null) {
        head = temp.prev;
    }
 
    return head;
}