Объединить k отсортированных списков в один отсортированный список

 Источник: https://leetcode.com/problems/merge-k-sorted-lists

Дан массив из k связных списокв lists, элементы в каждом идут в возрастающем порядке.

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

Пример 1:

Дано: lists = [[1,4,5],[1,3,4],[2,6]]
Результат: [1,1,2,3,4,4,5,6]
Пояснение: Исходные списки такие:
[
  1->4->5,
  1->3->4,
  2->6
]
если их объединить, то мы получим такой список:
1->1->2->3->4->4->5->6

Пример 2:

Дано: lists = []
Результат: []

Пример 3:

Дано: lists = [[]]
Результат: []

Ограничения:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] содержит элементы отсортированные в возрастающем порядке
  
• Скммарная длиннавсех списков не превышает 10^4.

Идея решения

Мы можем объединить два списка в один отсортированный за линейное время. Для этого мы сканируем оба списка и заносим в результат наименьший элемент.

Если у нас k списков, то мы можем объединить 1 с 2, потом итеративно с 3, и так далее, пока не исчерпаем все k списков. То есть мы просмотрим не более k раз все элементы списков, тога сложность будет O(kN), где N - сумма всех длин списков.

Если мы будем объединять k списков по методу "разделяй и властвуй". То есть мы предположим, что каким-то образом объединили пол-массива списков слева и пол-массива списков справа. В обоих случаях получили отортированный список. Тогда нам нужно в финале объединить два списка. Сложность такой операции log(k)N+N, что эквивалентно log(k)N.

Имплементация 

class Solution {

    // функция объединения двух списков
    private ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) return null;
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        // создаем пустой элемент,
        // который будет указывать на первый элемент результирующего списка
        ListNode temp = new ListNode();
        ListNode prev = temp;
        // для каждого списка используем свой пойнтер, оба пойнтера идут по спискам параллельно
        while (l1!= null && l2!=null) {
            // перенаправляем указатель на следующий элемент
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1=l1.next; // продвигаемся по l1
            }  else {
                prev.next = l2;
                l2 = l2.next; // продвигаемся по l2
            }
            prev = prev.next; // продвигаемся по результирующему списку
        }
        
        prev.next = l1 == null ? l2 : l1;

        return temp.next; // возвращаем первый элемент результирующего списка
    }

// функция, которая рекурсивно за k*log (k) объединяет k списков
// и возвращает список
    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start > end) return null; // нечего объединять
        if (start == end) return lists[start]; // у нас один список в наличии, его и вернем
        int mid = start + ((end - start) >> 1); // считаем пунт деления списков
// объединяем списки в левой части и в правой части рекурсивно
// получаем два списка, которые объедияем линейно функцией объединения двух списков
        return merge(merge(lists, start, mid), merge(lists, mid+1, end));
    }

// исходная функция
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) return null;
        if (lists.length == 1) return lists[0];
        return merge(lists, 0, lists.length - 1);
    }
}