Объедините два несортированных связанных списка, чтобы получить отсортированный список — набор 2

Опубликовано: 22 Сентября, 2022

Учитывая два несортированных связанных списка , L1 из N узлов и L2 из M узлов, задача состоит в том, чтобы объединить их, чтобы получить отсортированный односвязный список .

Примеры:

Input: L1 = 3→5→1, L2 = 6→2→4→9
Output: 1→2→3→4→5→6→9

Input: L1 = 1→5→2, L2 = 3→7
Output: 1→2→3→5→7

Примечание. Здесь был рассмотрен подход с эффективным использованием памяти, который решает эту проблему в O (1) Auxiliary Space,

Подход: Идея состоит в том, чтобы использовать вспомогательный массив для хранения элементов обоих связанных списков, а затем отсортировать массив в порядке возрастания. И, наконец, вставьте все элементы обратно в связанный список. Выполните следующие шаги, чтобы решить проблему:

  • Объедините два списка, указав следующий из хвостовых узлов первого списка, L1 , на первый узел второго списка, L2 .
  • Пройдите по связанному списку L1 и поместите все элементы в вектор V .
  • Отсортируйте вектор V в порядке возрастания.
  • После сортировки вставьте все элементы обратно в список L1 .

Ниже приведена реализация описанного выше подхода:

Временная сложность: O((N+M)*log(N+M))
Вспомогательное пространство: O(N+M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ