Прочитав эту статью, вы не только сможете решать подобные вопросы, но и узнаете о шаблонах быстрых и медленных указателей, стеках и некоторых других понятиях. Я скажу, что эта проблема относится к категории средних; поэтому постараюсь максимально детализировать.
Начнем с оглавления.
Оглавление
Начнем с описания проблемы.
Описание
Учитывая связанный список символов, выясните, является ли список палиндромом. Палиндром — это последовательность символов, которые одинаково читаются спереди и сзади. Например, на рисунке ниже связанный список, выделенный зеленым цветом, является палиндромом, а желтым — нет.
Еще несколько примеров прояснят ситуацию.
Example 1: Input: [1, 3, 5, 3] Output: No Explanation: The list is not the same from front [1, 3, 5, 3] as well as back [3, 5, 3, 1]. Example 2: Input: [8, 2, 3, 3, 2, 8] Output: Yes
Решение для стека
Есть два способа решить эту проблему с помощью структуры данных: один — с помощью массива, что не составляет труда, а другой — с использованием стека, который мы собираемся обсудить.
Решение на основе массива помещает содержимое связанного списка в массив и проверяет, равны ли элементы сзади элементам с самого начала. Эта проверка продолжается до середины массива, и если все совпадает, то это палиндром. Временная и пространственная сложность этого подхода составляет O(n).
Прежде чем обсуждать стековый подход, во-первых, мы должны знать, ПОЧЕМУ стек. А ответ — в определении палиндрома. Последовательность является палиндромом, если она идентична самой себе в обратном порядке. Здесь пригодится стек, поскольку он следует принципу LIFO (последним пришел, первым вышел). Когда мы вынимаем элементы из стека, они идут в обратном порядке.
Алгоритм
- Поместите все узлы связанного списка в стек. Теперь вершина стека — это последний элемент связанного списка.
- Запустите цикл while, чтобы пройти узел за узлом связанного списка и на каждой итерации сравнить текущий узел с вершиной стека.
- Если они имеют одинаковый символ, то переходим к следующей итерации и также выталкиваем вершину стека, так как мы уже сравнили ее с узлом.
- Если на какой-либо итерации мы находим несоответствие, то возвращаем false (не палиндром).
- Если цикл завершается без совпадений, возвращаем true (палиндром).
Давайте посмотрим на рабочий пример, используя цифры. У нас есть связанный список и стек следующим образом.
Сначала пройдемся по связанному списку и добавим все узлы в стек, чтобы при извлечении элементов они выводились в обратном порядке. Ведь мы хотим проверить, одинаков ли список спереди (используя сам связанный список) и сзади (используя стек).
Сравните первый элемент связанного списка (5) с вершиной стека (5) и извлеките стек. Они равны, поэтому переходим к следующим двум элементам.
Далее обе структуры данных имеют 1 в качестве текущего элемента.
Тогда текущие элементы 4 и 4.
Опять же, 4 и 4 равны.
Следующая итерация указывает на узел с 1, и вершина стека также равна 1.
В конце концов, в обоих местах есть «5».
Поскольку несоответствий мы не встретили, связанный список представляет собой палиндром.
Ниже приведен пример несоответствия, если связанный список не является палиндромом. Вы можете видеть, что первый элемент связанного списка не совпадает с последним элементом (вершиной стека).
Код очень прост; мы собираемся использовать встроенный стек, который доступен во всех основных языках, таких как cpp, Python, java и т. д.
Код
Сложность
Время: поскольку мы проходим по связанному списку один раз, чтобы поместить все элементы в стек, временная сложность равна O(n), где n — размер связанного списка.
Пробел: мы используем стек для хранения элементов связанного списка; следовательно, пространственная сложность равна O(n).
Итеративное решение (обратное)
Следует также отметить, что вторая половина палиндрома является зеркальным отражением первой половины; другими словами, вторая половина обратна первой половине. Если мы перевернем последнее и сравним его с первым, оно будет идентичным в палиндроме.
Алгоритм
- Разделите связанный список на две половины.
- переверните вторую половину.
- Пройдитесь по обоим спискам узел за узлом, чтобы проверить, идентичны ли они.
- Если полностью идентичны, то исходный список является палиндромом.
- В противном случае это не так.
Для разделения связанного списка на две половины мы будем использовать быстрый и медленный указатели. Оба начнут с головы, быстрый будет пропускать прыжок на два узла (в два раза быстрее), а медленный будет перемещаться по одному узлу за раз. Из-за этого к тому времени, когда slow достигнет половины, указатель fast достигнет конца связанного списка.
В конце концов, после проверки на палиндром, мы также превратим два списка в исходный. Давайте посмотрим на пример в действии, используя следующие рисунки.
Мы разделили приведенный выше список на две части, используя шаблон быстрого и медленного указателей.
Второй связанный список реверсируется с помощью техники, которую мы обсуждали в нашей статье Реверсирование связанного списка.
Пройдите два связанных списка одновременно, используя цикл, и проверьте, равны ли все соответствующие узлы. На рисунке ниже два списка идентичны; следовательно, исходный связанный список является палиндромом.
Код
Сложность
Время: связанный список просматривается, чтобы найти среднюю точку и снова сравнить первую половину со второй половиной. Следовательно, временная сложность равна O(n).
Пробел: мы не используем память; следовательно, пространственная сложность постоянна.
И это все для этой проблемы; встретимся в следующей задаче связанного списка.
Если вам понравилось то, что вы только что прочитали, мы будем очень признательны за хлопки🤗🤗🤗. Вы можете щедро хлопать в ладоши; это показывает мне, насколько вам понравилась эта история. А если не понравилось? Пожалуйста, оставьте комментарий😋!
P.S.: Если вам нравится этот непрерывный опыт чтения на этой прекрасной платформе Medium.com, подумайте о том, чтобы поддержать авторов этого сообщества, подписавшись на членство ЗДЕСЬ. Он стоит всего 5 долларов США в месяц и поддерживает всех авторов.
Вы также можете подписаться на меня ЗДЕСЬ, чтобы получать новости о моих историях.
