题目

合并K个升序链表

https://leetcode-cn.com/problems/merge-k-sorted-lists/

公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注

描述

难度：困难

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：
  
[
  1->4->5,
  1->3->4,
  2->6
]
  
将它们合并到一个有序链表中得到
  
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

Solution

合并解法

解题思路

给你一个链表数组，每个链表都已经按升序排列

请你将所有链表合并到一个升序链表中，返回合并后的链表

提取下关键信息

• 链表数组，且每个链表已按照升序排列好
• 合并链表

链表是通过指针来进行链接多个对象，形成对象链的一种数据结构，本题中ListNode对象中next变量充当指针作用，指向下一个ListNode对象，既然是已经升序排列的链表，首先想到的粗暴解法就是进行链表合并，两个链表相互合并，合并之后的结果与剩余的链表合并，得到最终结果，核心合并递归代码如下

public ListNode merge2List(ListNode node1,ListNode node2){
  	//node1为null，则直接返回node2
        if(node1==null){
            return node2;
        }
  	//node2为null，直接返回node1
        if(node2==null){
            return node1;
        }
  	//当前node1的值 < node2的值，则进行node1.next的值与node2判断，依次递归，并且将合并的结果链接到node1.next
        if(node1.val<node2.val){
            node1.next=merge2List(node1.next,node2);
            return node1;
        }else{
         //同理
            node2.next=merge2List(node2.next,node1);
            return node2;
        }
    }

• 判断node1，node2是否为null，返回相对应的node
• 当前node1的值 < node2的值时，则进行node1.next的值与node2合并判断，依次递归，并且将合并的结果链接到node1.next，形成链表，最终返回合并后的值最小的node，即node1
• 同理，当前node2的值 <= node1的值时，则进行node2.next的值与node1合并判断，依次递归，并且将合并的结果链接到node2.next，形成链表，最终返回合并后的值最小的node，即node2

CODE

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
      	//结果res
        ListNode res = null;
        for(int i=0;i < lists.length; i ++){
          //合并两个链表，并且将合并后的结果赋值给res
           res = merge2List(res,lists[i]);
        }
        return res;
    }

   public ListNode merge2List(ListNode node1,ListNode node2){
  	//node1为null，则直接返回node2
        if(node1==null){
            return node2;
        }
  	//node2为null，直接返回node1
        if(node2==null){
            return node1;
        }
  	//当前node1的值 < node2的值，则进行node1.next的值与node2判断，依次递归，并且将合并的结果链接到node1.next
        if(node1.val<node2.val){
            node1.next=merge2List(node1.next,node2);
            return node1;
        }else{
         //同理
            node2.next=merge2List(node2.next,node1);
            return node2;
        }
    }
}

结果

• 执行用时：282 ms, 在所有 Java 提交中击败了10.62%的用户
• 内存消耗：41 MB, 在所有 Java 提交中击败了5.11%的用户

分治解法

优化思路

在上面解法里面，我们需要在合并后的基础上重新合并新的链表，越合并到最后，合并的过程越复杂，我们可以使用分治的思想，提前将链表进行两两合并，降低整体合并时间复杂度

CODE

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeList(lists,0,lists.length-1);
    }
	//分治，将开始结束下标传入，计算中间位置，拆分为两个链表，再进行合并
    public ListNode mergeList(ListNode[] list , int start,int end){
        if(start==end){
            return list[start];
        }
      	//计算中间位置
        int half = start + (end-start)/2;
        //start 到 中间位置 再进行拆分合并
        ListNode startNode = mergeList(list,start,half);
        //half 到 结束位置 再进行拆分合并
        ListNode endNode   = mergeList(list,half+1,end);
        //合并
        return merge2List(startNode,endNode);
    }



    public ListNode merge2List(ListNode node1,ListNode node2){
  	//node1为null，则直接返回node2
        if(node1==null){
            return node2;
        }
  	//node2为null，直接返回node1
        if(node2==null){
            return node1;
        }
  //当前node1的值 < node2的值，则进行node1.next的值与node2判断，依次递归，并且将合并的结果链接到node1.next
        if(node1.val<node2.val){
            node1.next=merge2List(node1.next,node2);
            return node1;
        }else{
         //同理
            node2.next=merge2List(node2.next,node1);
            return node2;
        }
    }
}

结果

• 执行用时：3 ms, 在所有 Java 提交中击败了76.21%的用户
• 内存消耗：41 MB, 在所有 Java 提交中击败了5.11%的用户

LeetCode名句

为啥我直接把官方题解的代码复制粘贴还会报错？？？