234. Palindrome Linked List

Задача

Дана head (голова) односвязного списка, верните true , если он является палиндромом, или false в противном случае.

Примеры

Пример 1

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

Пример 2

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

Решение

Решение

 // Временная сложность: O(N) - Проходим по списку несколько раз (поиск середины, разворот, сравнение, восстановление), что в сумме дает линейное время.
 // Пространственная сложность: O(1) - Используем только константное количество переменных-указателей, не выделяя дополнительную память пропорционально размеру списка.
 
 var isPalindrome = function(head) {
     // 0. Базовые проверки
     if (!head || !head.next) return true;
 
     // --- ЭТАП 1: Находим середину ---
     let slow = head;
     let fast = head;
 
     while (fast && fast.next) {
         slow = slow.next;
         fast = fast.next.next;
     }
 
     // --- ЭТАП 2: Разворачиваем вторую половину ---
     // Функция-хелпер для разворота, так как нам она понадобится дважды
     const reverseList = (startNode) => {
         let prev = null;
         let curr = startNode;
         while (curr) {
             const nextTemp = curr.next;
             curr.next = prev;
             prev = curr;
             curr = nextTemp;
         }
         return prev; // Новая голова развернутого участка
     };
 
     // tail - это начало развернутой второй половины (бывший конец списка)
     let tail = reverseList(slow);
 
     // --- ЭТАП 3: Сравниваем две половины ---
     let p1 = head;
     let p2 = tail;
     let result = true; // Запоминаем результат, но не выходим сразу, чтобы успеть починить список
 
     while (result && p2) {
         if (p1.val !== p2.val) {
             result = false;
         }
         p1 = p1.next;
         p2 = p2.next;
     }
 
     // --- ЭТАП 4: Восстанавливаем список (разворачиваем вторую половину обратно) ---
     // Мы снова разворачиваем ту же часть, начиная с tail
     reverseList(tail);
 
     return result;
 };

Решение 2 (Array + Two Pointer)

// Временная сложность: O(n)
// Пространственная сложность: O(n).
 
var isPalindrome = function(head) {
    const vals = [];
    while (head) {
        vals.push(head.val);
        head = head.next;
    }
 
    let left = 0;
    let right = vals.length - 1;
    while (left < right) {
        if (vals[left] !== vals[right]) return false;
        left++;
        right--;
    }
    return true;
};

Решение 3 (мое)

// Мутирует входные данные
// Временная сложность: O(n)
// Пространственная сложность: O(n). Добавляем каждому узлу новое поле prev
 
var isPalindrome = function(head) {
    let node = head;
    let prev;
 
    while (node) {
        if (prev) {
            node.prev = prev;
        }
 
        prev = node;
        node = node.next;
    }
 
    node = prev;
    while (head && node) {
        if (head === node) return true;
        if (head.val !== node.val) return false;
 
        head = head.next;
        node = node.prev
    }
 
    return true;
};