Связанный список — это особая структура данных, о которой часто спрашивают на собеседованиях по программированию, но которая никогда не используется в реальной жизни. Поначалу они пугают, так как указатели обычно очень запутанны. Недавно я практиковался в решении некоторых из этих проблем на Leetcode, и большинство из них касалось того, как «творчески» манипулировать этими указателями. Как только вы поймете, как это использовать и как это работает, проблемы со связанными списками станут менее пугающими. Также существует не так много различных типов вопросов со связанными списками, поэтому, ответив на несколько вопросов, вы можете в основном ответить на любые другие.

Этот пост был бы больше похож на документ для себя о проблемах, с которыми я столкнулся. Мыслительный процесс здесь может быть либо моими мыслями, которые привели к моему решению , либомоим пониманием того, как работает решение других людей (которое я нашел) и как они думают об этом (или, по крайней мере, я так думаю). они думали).

Пост получился слишком длинным, поэтому я разобью его на 2 части. Нажмите здесь, чтобы перейти к части 2.

Несколько наблюдений, которые у меня были после решения нескольких из этих задач:

  • Никогда не используйте head TreeNode для прямого просмотра или изменения списка. Если мы сделаем это, мы потеряем исходный список — односвязный список не может быть повторен в обратном направлении.
  • Иногда мы можем создать новый TreeNode, указатель .next которого указывает на head. Он рассматривается как фиктивный указатель. Основная причина, по которой нам это нужно, заключается в том, что нам нужен способ вернуться к началу списка результатов.
  • Чтобы удалить узел из списка, нам нужен узел до этого. Мы просто обновляем его следующий указатель, чтобы пропустить узел, который мы хотим удалить.

Теперь давайте углубимся в некоторые вопросы кодирования.

1. Удалить дубликаты из отсортированного списка

Код на GitHub с комментариями

Ввод: отсортированный связанный список (по возрастанию)

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. Нечетно-четный связанный список

Код на GitHub с комментариями

Ввод: односвязный список.

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) пространственная сложность без дополнительных структур данных.

До скорого. Приятного чтения!