Связанный список — это особая структура данных, о которой часто спрашивают на собеседованиях по программированию, но которая никогда не используется в реальной жизни. Поначалу они пугают, так как указатели обычно очень запутанны. Недавно я практиковался в решении некоторых из этих проблем на Leetcode, и большинство из них касалось того, как «творчески» манипулировать этими указателями. Как только вы поймете, как это использовать и как это работает, проблемы со связанными списками станут менее пугающими. Также существует не так много различных типов вопросов со связанными списками, поэтому, ответив на несколько вопросов, вы можете в основном ответить на любые другие.
Этот пост был бы больше похож на документ для себя о проблемах, с которыми я столкнулся. Мыслительный процесс здесь может быть либо моими мыслями, которые привели к моему решению , либомоим пониманием того, как работает решение других людей (которое я нашел) и как они думают об этом (или, по крайней мере, я так думаю). они думали).
Пост получился слишком длинным, поэтому я разобью его на 2 части. Нажмите здесь, чтобы перейти к части 2.
Несколько наблюдений, которые у меня были после решения нескольких из этих задач:
- Никогда не используйте
head
TreeNode для прямого просмотра или изменения списка. Если мы сделаем это, мы потеряем исходный список — односвязный список не может быть повторен в обратном направлении. - Иногда мы можем создать новый TreeNode, указатель
.next
которого указывает наhead
. Он рассматривается как фиктивный указатель. Основная причина, по которой нам это нужно, заключается в том, что нам нужен способ вернуться к началу списка результатов. - Чтобы удалить узел из списка, нам нужен узел до этого. Мы просто обновляем его следующий указатель, чтобы пропустить узел, который мы хотим удалить.
Теперь давайте углубимся в некоторые вопросы кодирования.
1. Удалить дубликаты из отсортированного списка
Ввод: отсортированный связанный список (по возрастанию)
1 -> 2 -> 3 -> 4 -> 4 -> 5
Вывод: связанный список только с разными номерами.
1 -> 2 -> 3
Мыслительный процесс:
Хорошая вещь в этой проблеме заключается в том, что список отсортирован, поэтому, если число дублируется, мы могли бы сразу это узнать, переместив указатель, чтобы проверить следующий элемент. Однако для этого нам нужно «сохранить» или как-то пометить текущее число, чтобы при переходе к следующему элементу мы могли свериться с этим сохраненным значением.
Это приводит к идее иметь 2 указателя. Назовем их startPointer
и endPointer
. Но как мы используем эти 2 указателя? startPointer
используется для обозначения начала дублированной последовательности. endPointer
продолжит обход и сделает все, что нужно (мы к этому еще вернемся).
Другой вопрос, должны ли мы поставить startPointer
на первый найденный дубликат или на элемент прямо перед ним (это означает, что startPointer.next
будет началом дублированной последовательности)? Это приводит к следующему пункту.
Например, мы решили поместить startPointer
в первый элемент дублированной последовательности. Возникает еще одна проблема: скажем, после обнаружения нескольких дубликатов и удаления их из списка, если следующий элемент НЕ похож на значение в startPointer
, нам нужно удалить узел в startPointer
. Это вызывает проблему, потому что мы можем удалить его, только обновив указатель .next
элемента перед ним, а с односвязным списком мы не могли вернуться обратно.
Итак, кажется, что startPointer
должно быть до начала такой последовательности. А как насчет endPointer
?
Очевидно, что endPointer
должен двигаться быстрее, чем startPointer
. Но как быстро? Сначала я думал, что просто перемещу endPointer
и удалю дубликаты один за другим. Но я понял, чтобы удалить узел, мне нужен доступ к предыдущему узлу, которого у меня не было бы, если бы я удалял по одному. Лучшим решением было бы удалить всю дублированную последовательность.
Мы могли бы использовать endPointer
в качестве разведчика, перемещаясь на 1 шаг перед startPointer
и проверяя, совпадает ли следующий элемент endPointer.next
с самим endPointer
или нет. Если нет, то для startPointer
«безопасно» перейти к текущему endPointer
. Это гарантирует, что startPointer
всегда находится за 1 узел до начала дубликатов. Поэтому мы продолжаем обход endPointer
до тех пор, пока endPointer.next
не станет дублирующимся значением.
Другими словами, если текущее значение endPointer
равно значению endPointer.next
, мы продолжаем двигаться вперед на endPointer
, пока они не станут разными. К этому времени дублированные значения находятся в диапазоне от startPointer.next
до endPointer
.
Теперь, если мы хотим пропустить всю дублированную последовательность, просто сделайте так, чтобы startPointer.next
указывало на endPointer.next
.
- If they are pointing to the same thing then there has been no duplication yet, hence move both pointers. Fast forward... - Now, start.next is 3 and end is at 3 also dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null ^ ^ start end - As end.val == end.next.val, we move end forward dummy -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null ^ ^ -->^ start end->end - Now, start.next is still node 3 (Node that has value 3 and point to another 3), whereas end is now pointing to node with value 3 but its next pointer POINT TO 4. Meaning the duplicated sequence is identified. dummy -> 1 -> 2 3 -> 3 -> 4 -> 4 -> 5 -> null ^ ^ start end ... 2 ------------> 4.. - Update node 2 to point to end.next, which is 4, skipping all duplicated val
Сложность во времени и пространстве:
O(n) временная сложность, начиная с endPointer
, которая выполняет «тяжелую работу» по обходу списка один раз, где n — количество узлов в списке.
O(1) пространственная сложность, поскольку нет дополнительной структуры данных. использовал
2. Нечетно-четный связанный список
Ввод: односвязный список.
2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 -> NULL
Вывод: связанный список с узлами с нечетной группой индексов слева и узлами с четной группой индексов справа (обратите внимание, что в этом случае индекс начинается с единицы, поэтому первый узел находится в индексе 1)
2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4 -> NULL
Мыслительный процесс:
Моя мысль заключалась в том, чтобы сделать исходный список моим списком со всеми узлами индекса odd
и создать другой список для всех узлов индекса even
. Затем, когда я просматриваю исходный список, пропускаю индекс even
и помещаю эти четные узлы во второй список. Наконец, объедините их вместе, чтобы конец списка odd
указывал на начало списка even
.
Должно быть задействовано 4 указателя:
- Начало списка
odd
:head
- Указатель для обхода нечетного списка:
oddPointer
- Начало списка
even
:evenListHead
- Указатель для обхода четного списка:
evenPointer
oddPointer
должно начинаться как head
. Принимая во внимание, что evenPointer
должен быть следующим узлом. evenListHead
в этом случае будет первым четным узлом, на который временно указывает evenPointer
.
Условие для цикла while может быть немного сложным. Так как evenPointer
стартует немного быстрее, чем oddPointer
на 1 узел впереди, и мы хотим «виртуально» сократить список пополам, то нам нужно проверить 2 условия:
- Если
evenPointer
неnull
(после последнего узла — в случае, если в списке нечетное количество узлов) - И если
evenPointer.next
неnull
(evenPointer
на последнем узле — в случае, если в списке четное количество узлов)
Внутри петли 4 шага. Поскольку oddPointer
запускается медленнее, сначала обрабатываем его:
- Обновите
oddPointer.next
, чтобы он указывал на следующий нечетный узел, пропуская четный узел - Переместите
oddPointer
к следующему нечетному узлу - Обновите
evenPointer.next
, чтобы он указывал на следующий четный узел после текущегоoddPointer
. - Переместите
evenPointer
к следующему четному узлу
Мы просто манипулируем текущими указателями, пропуская нечетные/четные узлы, а затем объединяем их в конце. Пока цикл не завершится, evenListHead
все еще указывает на первый четный узел исходного списка; и head
по-прежнему является началом исходного списка или, в конечном счете, списка результатов.
Я нахожу указатели довольно запутанными: хотя evenListHead
присваивается evenPointer
, по мере продвижения evenPointer
evenListHead
нет. evenPointer
может манипулировать текущим узлом, чтобы указать на следующий узел, но когда он перемещается к следующему узлу, это не означает, что evenListHead
также перемещается. Суть указателя в том, что речь идет о ссылке — указании на адрес в памяти. Думайте об этом как о адресе текущего узла 123
, который изначально назначен как evenListHead
, так и evenPointer
. Когда evenPointer
«перемещается» к следующему узлу с адресом 456
, evenListHead
все еще находится в 123
.
Сложность времени и пространства:
Временная сложность O(n), поскольку список проходится только один раз, где n — количество узлов в списке.
O(1) пространственная сложность без дополнительных структур данных.
До скорого. Приятного чтения!