Сложность: easy
Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.
Пример:
Input: head = [1,2,2,1]
Output: true
👨💻 Алгоритм:
1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null.
2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся.
3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата.
😎 Решение:
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
vals = []
currentNode = head
while currentNode is not None:
vals.append(currentNode.val)
currentNode = currentNode.next
front = 0
back = len(vals) - 1
while front < back:
if vals[front] != vals[back]:
return False
front += 1
back -= 1
return True
Ставь 👍 и забирай 📚 Базу знаний