Вопрос по LeetCode 234. Palindrome Linked List (Java)

Рейтинг: -3Ответов: 1Опубликовано: 09.08.2023

Я недавно на Java начал программировать, решил порешать стандартные задачки. Решил обычные палиндромы, там мне все понятно. Зашел на палиндромный линкед лист и ничего не понял. Пошел смотреть решения.

Объясните мне пожалуйста, почему в этой задаче все делают какие-то два курсора, идут по списку разделяют его на две части и так далее? Почему нельзя просто развернуть список как в случае с обычным палиндромом, путем например создания второго LinkedList, и потом просто их сравнить?

Например:

List<Integer> list1 = new LinkedList<>();
List<Integer> list2 = new LinkedList<>();

for(int i = list1.size() - 1; i >= 0; i--) {
    list2.add(list1.get(i))
}

Ответы

▲ 2Принят

Вообще условие задачи полагается приводить здесь.

Видимо, в конце вы не заметили приписку:

Follow up: Could you do it in O(n) time and O(1) space?

что исключает создание второго списка (в этом случае память O(n)).

Без этого требования - да, можно список целиком развернуть и сравнить.