23.合并K个有序列表

秒速五厘米 2021-09-17 10:02 265阅读 0赞

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

示例:

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

方法一：想必做这道题之前，都有合并过两个链表吧，两个链表的合并代码如下：

public static ListNode merge(ListNode p,ListNode q){
        if(p==null)
            return q;
        if(q==null)
            return p;
        ListNode head = null;
        ListNode rear = null;
        while(p!=null && q!=null){
            if(p.val < q.val){
                if(head==null){
                    head = p;
                    rear = head;
                }else{
                    rear.next = p;
                    rear = p;
                }
                p = p.next;
            }else{
                if(head==null){
                    head = q;
                    rear = head;
                }else{
                    rear.next = q;
                    rear = q;
                }
                q = q.next;
            }
        }
        if(p!=null){
            rear.next = p;
        }
        if(q!=null){
            rear.next = q;
        }
        return head;
    }

而合并K个链表？是不是可以**分为多次两个链表的合并**？这样我们便可以完成K个链表的合并。代码如下：

public static ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)
            return null;
        ListNode head = lists[0];
        for(int i=1;i<lists.length;i++){
            head = merge(head,lists[i]);
        }
        return head;
    }

方法二：类似于合并两个链表，不过这次是起头并进进行合并。数组中的每一个元素都是一个链表，那么每次在链表头中选最小一个，同时将该链表的表头向后移动。  
代码如下：

public static ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)
            return null;
        int len = lists.length;
        ListNode head = null;
        ListNode rear = null;
        while(true){
            int min = Integer.MAX_VALUE;
            int index = -1;//记录最小值在数组中的下标
            for(int i = 0;i < len;i++){
                if(lists[i]!=null){
                    if(lists[i].val < min){
    	                    min = lists[i].val;
                        index = i;
                    }
                }
            }
            if(index==-1){//当数组元素都为空时，即可退出
                break;
            }else{
                if(head==null){
                    head = lists[index];
                    rear = head;
                    lists[index] = lists[index].next;
                }else{
                    rear.next = lists[index];
                    rear = lists[index];
                    lists[index] = lists[index].next;
                }
            }
    
        }
      return head;
    }