LeetCode #23. Merge k Sorted Lists プログラミング練習

問題：

難易度:　hard
入力:　ListNodeのリスト
目的: 入力されたLinkedLIstをマージせよ
出力:　ListNode

♯21問めに、二つのソートされたLinkedListをマージする問題がありましたが、
今回はそれの延長問題です。
21問目と同様、入力のリスト群はすべてソートされています。
難点はリストが二つだけではないので、次の数字がどのリストに入っているのかがわからないところです。

注意すべき事:　

• 全体探索をするとO(n^k)で時間がTLEになってしまう。

以下回答です。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return helper(lists, 0, lists.length-1);
    }
    
    public ListNode helper(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        if (left < right) {
            int mid = (left + right)/2;
            ListNode l1 = helper(lists, left, mid);
            ListNode l2 = helper(lists, mid+1, right);
            return merge(l1, l2);
        }
        else return null;
    }
    
    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = merge(l1.next,l2);
            return l1;
        }
        else {
            l2.next = merge(l1, l2.next);
            return l2;
        }
    }
}

recursiveとpartitionを使った回答です。
mergeの関数は#21問目と全く同じです。
二つのソートされたLinkedListをマージする関数です。
それに加え、Partitionを使っています。
それにより入力されたリスト群を二つずつマージしていく方法です。
Time complexity は O(nklogk)になります。

以上。
よいプログラミング生活を！