Что касается темы связанных списков, я думаю, что это будет проблема средней категории. Я подробно объяснил три решения (отсортированные по эффективности), каждое из которых лучше, чем предыдущий подход. Давай начнем! 😀 Работать со связанными списками всегда интересно.
Если вы готовитесь к собеседованию по программированию, этот список вам поможет. Я составил 30-дневный план для подготовки к написанию кода (конечно, вы можете занять больше времени).
Оглавление
- Описание
- Решение грубой силы
- Линейное решение с использованием хеш-таблицы
- Код
- Линейное решение и постоянное пространство
- Код
Описание
Нам даны два связанных списка (головы), но из-за какой-то ошибки последний узел второго связанного списка указывает на какой-то узел первого списка, образуя Y-подобную структуру. Найдите узел первого списка, к которому присоединен второй список.
Например, на рисунке ниже нам даны два списка с двумя отдельными указателями на заголовки.
Но узел второго списка с данными «Е» указывает на «С», и мы хотим найти указатель на узел С.
Решение грубой силы
Каждый раз, когда вы сталкиваетесь с вопросом, прочитав описание и несколько примеров, спросите себя, как проще всего и понятнее достичь решения, не задумываясь о сложности (улучшайте решение постепенно).
В этом случае мы хотим знать, какой первый узел является общим для обоих списков. Для этого мы будем проходить по первому списку, узел за узлом, и для каждого узла первого списка мы будем проходить по второму списку. Если мы найдем текущий узел из первого списка во втором списке, это наш ответ.
Для приведенного выше примера грубая сила будет работать следующим образом. Первый узел в списке 1 — это «A», проверьте, присутствует ли он в списке 2.
Затем проверьте наличие следующего узла в списке 1, «B».
Действуя таким образом, мы найдем следующий узел «C», проходя по второму списку.
Алгоритм метода грубой силы
- Запустите два цикла со вторым циклом, вложенным в первый.
- Внешний цикл проходит по первому списку, а внутренний цикл — по второму.
- Для каждого узла, на который указывает внешний цикл, проверьте, присутствует ли он во втором списке, используя внутренний цикл.
- Если да, то этот узел является ответом.
Код вышеописанного алгоритма выглядит следующим образом:
Полный код
Прочитайте функцию findIntersection() ниже.
Output: list 1: A->B->C->D->NULL list 2: E->C->D->NULL The intersection point is C
Сложности времени и пространства
Время: используются два вложенных цикла, где внешний цикл выполняется m раз, а внутренний цикл выполняется n раз. Следовательно, временная сложность равна O(m*n), где m — размер первого списка, а n — размер второго. второй список.
Пробел: здесь не используется дополнительный пробел. Но в следующем решении мы будем использовать структуру данных для улучшения временной сложности.
Линейное решение с использованием хеш-таблицы
В предыдущем примере нам приходилось повторно проходить второй цикл, потому что мы хотели знать, содержит ли второй список какой-либо общий узел с первым. Одним из эффективных решений является запоминание всех узлов первого списка и обход второго списка.
Если мы встретим узел, который уже есть в первом списке (мы это знаем, потому что запомнили все узлы первого списка), то этот узел и будет нашим ответом. Давайте применим этот подход к предыдущей задаче.
Пройдите по первому связанному списку и поместите узлы в хеш-таблицу.
Теперь, когда мы пройдем по списку 2, мы проверим каждый узел на его присутствие в хеш-таблице.
Код
Прочитайте функцию findIntersection() ниже.
Output: list 1: A->B->C->D->NULL list 2: E->C->D->NULL The intersection point is C
Сложность времени и пространства
Время: временная сложность является линейной, поскольку мы используем один цикл, который проходит по второму списку.
Пробел: в этом подходе мы используем хэш-таблицу, в которой хранятся узлы первого списка. Следовательно, пространственная сложность равна O(n), где n — размер списка 1.
Эффективное решение (линейное время и постоянное пространство)
Мы можем видеть, что если бы два связанных списка были одинакового размера, мы могли бы пройти по обоим спискам одновременно и вернуть первый узел, общий для обоих. Но наши связанные списки могут иметь разные размеры.
Наш подход заключается в обходе большего списка для некоторых узлов, чтобы оба списка были равны по размеру. Предположим, что размер списка 1 равен size1, а размер списка 2 равен size2, тогда нам нужно пройти по большему списку для первого abs(size1-size2) узлы. Затем просматривайте оба списка одновременно, пока не найдете общий узел. Этот общий узел и есть наш ответ.
Найдя размеры, ставим указатель на узел B. Теперь список1 начнет обход с узла B, а список2 — с узла E.
В тот момент, когда мы обнаруживаем, что узел C является общим для обоих списков, мы останавливаем наше решение.
Алгоритм следующий.
- Найдите размеры обоих списков. Допустим, размеры list1 и list2 равны size1 и size2.
- Начните обход большего списка от головного узла к следующим узлам abs(size1-size2).
- Теперь оба списка имеют равные узлы, которые нужно пройти.
- Пройдите оба списка одновременно и, если вы найдете общий узел, верните его.
Код
Сложность времени и пространства
Время. Временная сложность – O(m), где m – размер самого большого связанного списка. Потому что сначала мы прошлись по некоторым узлам большего списка, а затем по оставшимся узлам вместе с узлами другого списка.
Пробел: дополнительный пробел не используется.
Спасибо!! Надеюсь, статья вам понравилась и оказалась полезной.
Если вам понравилось то, что вы только что прочитали, мы будем очень признательны за хлопки🤗🤗🤗. Вы можете щедро хлопать в ладоши; это показывает мне, насколько вам понравилась эта история. А если не понравилось? Пожалуйста, оставьте комментарий😋!
P.S.: Если вам нравится этот непрерывный опыт чтения на этой прекрасной платформе Medium.com, подумайте о том, чтобы поддержать авторов этого сообщества, подписавшись на членство ЗДЕСЬ. Это стоит всего 5 долларов США в месяц и помогает всем авторам.
Вы также можете подписаться на меня ЗДЕСЬ, чтобы получать обновления моих историй
