Проблемы со связанными списками поначалу могут показаться сложными, но они не так уж и плохи, как только вы освоитесь с ними. По крайней мере, так они говорят. Мне еще предстоит дойти до этого момента, вот почему я здесь пишу об этом в блоге! Если вы новичок в связанных списках, ознакомьтесь с этим сообщением . В то время как обращение связанных списков и поиск циклов являются большими проблемами для начала, эта проблема с нечетным четным списком также довольно хороша для нас, начинающих. Давайте начнем!
Проблема в том,
Учитывая односвязный список, сгруппируйте все нечетные узлы вместе, за которыми следуют четные узлы. Пожалуйста, обратите внимание, что здесь мы говорим о номере узла, а не о значении в узлах.
Ссылка на проблему
Проверьте рисунок А для примера ввода и результата.
Как решить
Для решения этой проблемы мы создадим два связанных списка. Один из связанных списков будет содержать все нечетные узлы из исходного списка, а другой список будет содержать все четные узлы из исходного списка. Как только у нас будут эти два списка, список событий будет добавлен в конец нечетного списка.
В этом примере узлы списка просто случайно имеют значения, соответствующие их расположению в списке. Просто напоминание о том, что проблема гласит, что “мы говорим о номере узла, а не о значении в узлах”.
Код
Давайте взглянем на код для решения этой проблемы. Прочитайте код и придайте ему как можно больше смысла. Затем мы можем пройти через это шаг за шагом и убедиться, что мы полностью понимаем это.
Вот шаги, которые выполняет алгоритм:
Создайте 5 новых узлов: нечетный, четный, нечетный узел, узел событий и текущий.
нечетная голова и четная голова не двигаются во время этого алгоритма. Они будут отслеживать начало четных и нечетных списков.
Текущий перебирает узлы списка, пока не достигнет значения null. На каждой итерации current узел, на который указывает current, будет либо подключен к концу нечетного списка, либо к четному списку.
Как только ток достигнет нуля, четный список будет подключен к концу нечетного списка.
Некоторые иллюстрации
Я знаю, что может быть полезно! Как насчет того, чтобы использовать некоторые иллюстрации, которые помогут нам лучше понять, что происходит в алгоритме.
Взгляните на рисунок B. Это показывает, что происходит в строках 15-21 кода. Это можно рассматривать как подготовительный шаг. Для проблем со связанными списками обычно требуется такой подготовительный этап, как этот. Я также хочу упомянуть, что головка все еще указывает на первый узел. Это просто не показано, чтобы сделать вещи немного яснее.
На рисунке C показано, что происходит в строках 23-25 кода. нечетный узел. следующий имеет значение текущий, текущий указывает на следующий узел, а добавить узел теперь указывает на то, где только что был текущий. Также обратите внимание, что нечетная голова остается на том же месте.
На рисунке D показано, что происходит в строках 27-29 кода. четный узел.следующий установлен в текущий, текущий указывает на следующий узел, и даже узел теперь указывает на то, где только что был текущий. Еще раз обратите внимание, что даже Голова остается на том же месте.
На рисунке E мы возвращаемся к строкам 23-25 кода. нечетный узел. следующий имеет значение текущий, текущий указывает на следующий узел, а добавить узел теперь указывает на то, где только что был текущий. Обратите внимание, что current теперь указывает на НУЛЬ.
На рисунке F применяются только строки 27-28 кода, потому что. четный узел.next имеет значение текущий, и четный узел указывает, где находится текущий. и цикл while завершается.
Теперь перейдем к строке 32 кода. нечетный узел. далее устанавливается в четный заголовок, что приводит к добавлению списка событий в конец нечетного списка. Оригинальная голова была возвращена на тот случай, если вы забыли, что она все еще там.
Выход:
result: [1, 3, 5, 2, 4]
Временная Сложность
Этот алгоритм будет иметь временную сложность O(n), где n – количество узлов в связанном списке.
Сложность пространства
Алгоритм работает в постоянном пространстве O(1).
Хотите узнать больше о Big-O? Я знаю отличное место для начала .
Совершенствуйтесь в алгоритмах!
Алгоритмы и структуры данных довольно сложны. Им определенно требуется время, чтобы я освоился с ними. Тем не менее, есть несколько замечательных ресурсов, и я чувствую себя обязанным поделиться некоторыми из них, которые были мне наиболее полезны. Если я пропустил что-то, что было вам полезно, обязательно упомяните об этом в комментариях.
Взлом интервью по кодированию — Отличный ресурс. Действительно настраивает вас на правильный лад для собеседований. Вы можете найти его здесь .
Элементы программирования Интервью — Еще одна замечательная книга. Лично мне это нравится больше, чем CTCI, но YMMV. Лично мне это нравится больше, чем CTCI, но YMMV. Вы можете найти его здесь .
Прослушивание интервью по кодированию — Не могу достаточно подчеркнуть это. Не видел, чтобы он упоминал об этом слишком часто. Объясняет закономерности, возникающие при различных проблемах с кодированием. Отлично подходит для представления общей картины всех различных проблем с алгоритмами, с которыми вы можете столкнуться. Проверить это здесь .
Спина К Спине SWE — Отличный Канал На YouTube . Очень рекомендую.
Кевин Нотон-младший. — Еще один потрясающий канал на YouTube . Отлично разбирается в проблемах и дает полезные советы.
База CS — Вайдехи Джоши проделывает огромную работу по изложению основ алгоритмов и структур данных. Ознакомьтесь с серией блогов здесь . У нее также есть подкаст , который я показываю двумя большими пальцами вверх.
Веб-сайт проблемы кодирования — Есть много разных вариантов на выбор. Хакерранк , Войны кодов , и Немного подредактировал все, похоже, довольно популярны. Я лично использую LeetCode . Найдите тот, который работает для вас!
Детская коляска — Делайте пародийные интервью! Чем скорее, тем лучше! Предусилитель оказал мне огромную помощь.
Что ж, надеюсь, это было полезно. Спасибо, что прочитали мой пост, и желаю удачи в изучении структур данных и алгоритмов!
Оригинал: “https://dev.to/danielleskosky/odd-even-linked-list-mdj”