leetcode第二十三題java解法--K個のソートチェーンテーブルをマージする

k個のソートチェーンテーブルをマージし、マージ後のソートチェーンテーブルを返します.アルゴリズムの複雑さを分析して説明してください.
例:

  :
[
  1->4->5,
  1->3->4,
  2->6
]
  : 1->1->2->3->4->4->5->6

構想:第21題で2つの秩序チェーンテーブルの拡張を統合するには、比較方法が必要であり、基本的には21題の解法である.今必要なのは2つの連結チェーンテーブルで、順番に連結するのは明らかに面倒です.そこで、i番目とi+mを比較(mはチェーンテーブルの長さの半分を指す)、m=(lists.length+1)/2させます.**どうして1を追加しますか?**チェーンテーブルの個数が奇数である場合、中間のチェーンテーブルをかすめることができるために、例えばa,b,c,d,eの5つのチェーンテーブルがあり、m=3で、cのチェーンテーブルがかすめられ、aとdが結合し、bとeが結合する.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n=lists.length;
        if(n==0)
            return null;
        while(n>1)
        {
            int m=(n+1)/2;
            for(int i=0;i<n/2;i++)// n/2
            {
                 lists[i]=compare(lists[i],lists[i+m]);
            }
            n=m;
        }
        return lists[0];
    }
    ListNode compare(ListNode x,ListNode y)
    {
        ListNode list=new ListNode(0);
        ListNode list2=list;
        while(x!=null&&y!=null)
        {
            if(x.val>y.val)
            {
                list.next=y;
                y=y.next;
            }
            else
            {
                list.next=x;
                x=x.next;
            }
            list=list.next;
        }
        if(y==null)
        {
            list.next=x;
        }
        else
        {
            list.next=y;
        }
        return list2.next;
    }
}