Merge K Sorted Lists
Задача: даны K связных списков, каждый из которых отсортирован. Необходимо написать алгоритм объединения заданных списков в единый отсортированный список.
Входные данные: lists — список списков
Вывод: result — результирующий список
Пример: 1->4->5, 1->3->4, 2->6
Output: 1->1->2->3->4->4->5->6
Разбор
Воспользуемся принципом разделяй и властвуй, в нашем случае, мы разделим задачу на 2 подзадачи:
- Напишем алгоритм для объединения 2х отсортированных связных списка.
- Далее пройдем по всем спискам и применим нашу подфункцию для 2х связных списка.
Как объединить 2 отсортированных связных списка?!
- Создаем два указателя для списков, а также создаем новый пустой список и указатель к нему.
2. Запускаем цикл покак оба указателя не равны null значению.
2.1. В цикле сравниваем значения узлов и присваиваем соот.значение новому списку, не забываем двигать указатели.
3. После окончания цикла, проверяем оба указателя: если какой то из них не равен null значению, значит в нем еще остались элементы, ктр присваиваем новому списку. Такая ситуация возникнет в том случае, если входные списки отличаются по длине.
Реализация
https://gist.github.com/unilecs/4fb9fc61f6c452a7cf394cfe3e904de8
