Связанный список - это линейная структура данных, состоящая из группы узлов, где каждый узел указывает на следующий узел через указатель. Каждый узел состоит из данных и ссылки (другими словами, ссылки) на следующий узел в последовательности.
Связанные списки - одни из самых простых и распространенных структур данных. Основные преимущества связанного списка перед обычным массивом:
- Элементы списка могут быть легко вставлены или удалены без перераспределения или реорганизации всей структуры, поскольку элементы данных не должны храниться в памяти непрерывно, а массив должен быть объявлен в исходном коде перед компиляцией и запуском программы.
- Связанные списки позволяют вставлять и удалять узлы в любой точке списка и могут делать это с постоянным числом операций, если ссылка, предшествующая добавляемой или удаляемой ссылке, сохраняется во время обхода списка.
С другой стороны, простые связанные списки сами по себе не позволяют произвольный доступ к данным или любую форму эффективного индексирования. Таким образом, многие базовые операции, такие как получение последнего узла списка или поиск узла, который содержит заданные данные, или определение места, куда должен быть вставлен новый узел, могут потребовать последовательного сканирования большинства или всех элементов списка. .
В этом посте мы перечислили часто задаваемые вопросы на собеседовании, в которых используется структура данных связанного списка:
- Введение в связанные списки
- Реализация связанного списка - C, C ++, Java, Python
- Связанный список - вставка в хвосте
- Статический связанный список
- Клонировать связанный список
- Удалить связанный список
- Вызвать операцию в связанном списке
- Вставить узел в его правильную отсортированную позицию в отсортированном связном списке
- Переупорядочить связанный список в порядке возрастания (Сортировать связанный список)
- Разделить узлы связанного списка на переднюю и заднюю половины
- Удалить дубликаты из отсортированного связного списка
- Переместить передний узел связного списка перед другим списком
- Переместить четные узлы в конец связанного списка в обратном порядке
- Разделить связанный список на два списка, каждый из которых содержит чередующиеся элементы
- Построить связанный список путем слияния альтернативных узлов двух заданных списков
- Объединить два отсортированных связанных списка в один
- Эффективное объединение` k` отсортированных связанных списков
- Пересечение двух отсортированных связанных списков
- Перевернуть связанный список - итерационное решение
- Обратный связанный список - рекурсивное решение
- Перевернуть каждую группу узлов` k` в связанном списке
- Найти k-й узел в конце связанного списка
- Объединить альтернативные узлы двух связанных списков в первый список
- Объединить два отсортированных связанных списка с их конца
- Удалять все« N узлов в связанном списке после пропуска узлов M »
- Упорядочить связанный список определенным образом за линейное время
- Проверить, является ли связанный список палиндромом
- Переместить последний узел в начало связанного списка
- Упорядочить связанный список определенным образом
- Определить цикл в связанном списке (алгоритм определения цикла Флойда)
- Сортировка связанного списка, содержащего 0, 1 и 2, за один проход
- Удалить дубликаты из связанного списка за один проход
- Переупорядочить связанный список так, чтобы в нем чередовались высокие и низкие значения
- Изменить порядок связного списка, отделяя нечетные узлы от четных
- Вычислить высоту двоичного дерева с листовыми узлами, образующими круговой двусвязный список
- Связанный список XOR - Обзор и реализация на C / C ++
- Рекурсивно проверять, является ли связанный список символов палиндромом
- Объединить два BST в двусвязный список в отсортированном порядке
- Удалить лишние узлы из пути, образованного связным списком
- Добавить однозначное число в связанный список, представляющий число
- Перевернуть каждую альтернативную группу узлов« k в связанном списке»
- Определить, является ли связанный список палиндромом
- Перевернуть двусвязный список
- Попарно поменять местами соседние узлы связного списка
- Свести связанный список
- Проверить, является ли связанный список строк палиндромным
- Свести многоуровневый связанный список
- Постройте сбалансированный по высоте BST из несбалансированного BST
- Поменять местами k-й узел с начала на k-й узел с конца в связанном списке
- Добавить два связанных списка, не используя лишнего места
- Клонировать связанный список со случайными указателями
- Обновить случайный указатель для каждого узла связанного списка, чтобы он указывал на максимальный узел
- Узлы ссылок присутствуют на каждом уровне двоичного дерева в виде связанного списка
- Преобразование тернарного дерева в двусвязный список
- Построить BST со сбалансированной высотой из отсортированного двусвязного списка
- Объединить на месте два отсортированных связанных списка без изменения ссылок первого списка
- Перевернуть указанную часть связного списка
- Найти точку пересечения двух связанных списков
- Извлечь листья двоичного дерева в двусвязный список
- Найдите вертикальную сумму двоичного дерева
- Преобразование двоичного дерева в двусвязный список на месте
- Найти тройку с заданной суммой в БСТ
- Проверить, совпадает ли обход заданных бинарных деревьев по листу
- Алгоритм сортировки слиянием для односвязного списка
- Сортировать двусвязный список с помощью сортировки слиянием
- Реализация стека с использованием связанного списка
- Реализация очереди с использованием связанного списка
- Преобразование двоичного дерева в двусвязный список по спирали
- Преобразование двоичного дерева поиска в минимальную кучу
- Преобразование многоуровневого связного списка в односвязный
- Распечатать узлы двоичного дерева в вертикальном порядке
Спасибо за чтение.