合并K个排序链表(java实现)

题目：

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

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
看到这道题，能想起来昨天我写的有一篇和这个题有些类似的博客，【合并两个有序的链表】

因此这个题的思路就是
　　1.k个有序的链表，根据我们之前做的那道题，应该采用两两合并，也就是累加法，最后合并到一起去
　　2.两个链表的长度可能不一样，我们需要考虑补全的问题。
代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = new ListNode(0);  //设置结果
        if(lists == null || lists.length < 0){
            return null;
        }else if(lists.length == 1){
            return lists[0];
        }else if(lists.length == 2){
            mergeTwoLists(lists[0],lists[1]);
        }else{
            res = mergeTwoLists(lists[0],lists[1]);
            for(int i = 2; i < lists.length;i++){
                mergeTwoLists(res,lists[i]);
            }
        }
        return res;
    }
    
    public ListNode mergeTwoLists(ListNode l1,ListNode l2){
        ListNode res = new ListNode(0);
        ListNode tmp = res;
        
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                tmp.next = l1;
                l1 = l1.next;
            }else{
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }
        //后面是为了补全的，因为链表的长度可能不一样
        if(l1 != null){
            tmp.next = l1;
        }else{
            tmp.next = l2;
        }
        return res.next;
    }
}

在别的博客中看到另一种解法，就是用优先队列，感觉挺高大上的，所以贴出来和大家分享，只是上面的方法我们容易理解一些罢了。

代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
       if(lists == null || lists.length < 0){
           return null;
       }
        PriorityQueue<Integer> queue = new PriorityQueue();
        for(ListNode node:lists){
            while(node != null){
                queue.add(node.val);
                node = node.next;
            }
        }
        ListNode res = new ListNode(0);
        ListNode tmp= res;
        while(!queue.isEmpty()){
            ListNode temp = new ListNode(queue.poll());
            tmp.next = temp;
            tmp = tmp.next;
        }
        return res.next;
    }
}

合并K个排序链表(java实现)

相关推荐