LeetCode-23.合并K个排序链表

╰+攻爆jí腚メ 2022-01-26 13:05 213阅读 0赞

# 题目 #

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

###### 示例: ######

> 输入: \[ 1->4->5, 1->3->4, 2->6 \]  
> 输出: 1->1->2->3->4->4->5->6

解题思路—**最小堆**：算法的**时间复杂度为O(Nlogk)**，其中k 是链表的数目，n 是链表的总节点数；**空间复杂度为O(N) (N>k)**。

> 新建一个长度为k的最小堆，**k个链表各将一个节点加入最小堆**，同时，**新建一个链表，每次弹出最小堆堆顶加入新的链表中，再将堆顶弹出的节点所属链表的下一个节点加入最小堆**。循环操作，直至链表中所有节点都加入了最小堆，并且**直至最小堆中元素全部弹出**。此时**新的链表即为k个链表的合并有序链表**。  
> 每次弹出堆顶，所需时间为O(logk)，所有节点都需要弹出，所以总时间复杂度为O(Nlogk)；因为新建了一个链表用来保存结果，所以空间复杂度为O(N)。

✨解题思路—**分治递归**：**推荐！！算法的时间复杂度为O(Nlogk)** ，其中k 是链表的数目，n 是链表的总节点数；**空间复杂度为O(1)**。

> **这一题可以说是分治算法的经典应用，分治算法的基本思想就是将一个规模为x的问题分解为y个规模较小的子问题,这些子问题相互独立且与原问题性质相同，求得子问题的解就可以求得原问题的解。**  
> 我们可以**将k个链表按对合并，即k个链表合并成k/2个链表，接下来k/4个链表，k/8个链表…，直到2个链表合并**，这就是分治解题的思想，**用递归来实现**。  
> 若O(n)为两个有序链表合并的时间复杂度，进行logk次操作，所以时间复杂度为O(Nlogk)；在链表合并过程中，只需要常数空间就可以实现，所以空间复杂度为O(1) 。

## Java解题—最小堆 ##

import java.util.PriorityQueue;
    import java.util.Queue;
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists==null || lists.length==0)
                return null;
    
            int num = lists.length;
            if(num==1)
                return lists[0];
            // lambda表达式自定义排序   
            Queue<ListNode> heap = new PriorityQueue<>(lists.length, (l1,l2)->{
                return l1.val-l2.val;
            });
            
            for(ListNode node:lists){
                if(node!=null)
                    heap.offer(node);
            }
            ListNode nhead = new ListNode(-1);
            ListNode head = nhead;
            while(!heap.isEmpty()){
                head.next = heap.poll();
                head = head.next;
                if(head.next!=null)
                    heap.offer(head.next);
            }
            return nhead.next;
        }
    }

## Java解题—分治递归 ##

class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists==null || lists.length==0)
                return null;
    
            int num = lists.length;
            if(num==1)
                return lists[0];
            return splitTwo(lists, 0, num-1);
        }
        
        // 分治递归
        public ListNode splitTwo(ListNode[] lists, int l, int r){
            if(l==r) return lists[l];
    
            int mid = l + (r-l)/2;
            return mergeTwo(splitTwo(lists, l, mid), splitTwo(lists, mid+1, r));
        }
    
        public ListNode mergeTwo(ListNode l1, ListNode l2){
            if(l1==null) return l2;
            if(l2==null) return l1;
    
            ListNode nhead = null;
            if(l1.val<l2.val){
                nhead = l1;
                nhead.next = mergeTwo(l1.next, l2);
            }else{
                nhead = l2;
                nhead.next = mergeTwo(l1, l2.next);
            }
            return nhead;
        }
    }