20200712——合并k个有序链表

合并k个有序链表 leetcode23

联想

• 合并2个有序链表

• 8赛道跑马

思路1

• 维护一个大小为k的数字，存储链表头。
• 对链表头元素进行冒泡，得到最小的元素，取出，放到结果链表resList
• 将最小元素的后一个节点放入数组，重新冒泡一次，得到新的最小元素，放入resList。
• 重复第3步，若有链表排完了，置为null，放到数组末尾（可以维护一个数组的有效大小arrRealSize）

复杂度分析

• 时间复杂度

每次冒泡k，取出一个元素。一共n个元素，那么应该是O（nk）

• 空间复杂度
  不考虑原始链表和结果链表，维护一个k的数组，应该是O（k）

思路2

对思路1稍稍改进
先进行一次排序O（klogk）
后续，只用对最小的元素的后续元素进行一次冒泡，那么平均复杂度可能大概是O（k/2）

O（k（logk+n/2））

public ListNode mergeKLists(ListNode[] lists) {
   
        int arrRealLength = lists.length;
        if (arrRealLength<=0) return null;
        //检查一遍数组元素是否为null
        for (int i = 0; i < arrRealLength; i++) {
   
            if (lists[i]==null){
   
                swap(lists,i,arrRealLength-- - 1);
                i--;
            }
        }
        for (int i = 0; i < arrRealLength; i++) {
   
            bubbleSort(lists,0,arrRealLength-1-i,false);
        }
        if (lists[0]==null) return null;
        //第1个元素，新链表的头
        ListNode newHead = new 

最后

以上就是香蕉眼神为你收集整理的20200712——合并k个有序链表的全部内容，希望文章能够帮你解决20200712——合并k个有序链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。