题目描述

合并k个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0<=n<=5000，每个节点的val 满足 |val|<=1000
要求：空间复杂度O(1)，时间复杂度O(nlogn)

例如：
输入：[{1,2,3},{4,5,6,7}]
返回值：{1,2,3,4,5,6,7}

题目分析

合并k个链表，因为链表是升序的，使用k个节点记录每个链表当前节点位置，每次只需要在这k个节点中选择一个最小的作为结果节点，且选择的链表也相应往后推，直到所有的链表都遍历完。如图： alt

解题思路

方法1：先获得链表的所有节点，然后对节点进行整体排序

最简单的做法就是使用一个列表存放链表的所有节点，对列表进行排序，然后按照列表的顺序将节点连接起来。对列表进行排序可以使用Collections.sort(）方法，默认是合并排序。

方法2：在k个链表节点中，不断按顺序获取节点可以减少整体排序的时间

虽然方法1的实现比较简单，但花费的时间也比较多，没有利用到链表本身的有序性，进行了很多不必要的比较，我们可以使用k个节点记录链表遍历位置，每次只需要对这K个节点进行比较，得到最小值即可，然后将其更换为该节点的下一个节点，直到所有的节点都遍历完成。

代码实现

方法1：对链表所有节点排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
    // 存储所有节点的列表
        ArrayList<ListNode> all = new ArrayList<>();
        for(ListNode node:lists){
            while(node != null){
            // 将节点放入列表中
                all.add(node);
                node = node.next;
            }
        }
        // 对所有节点进行排序，默认是合并排序
        Collections.sort(all, new Comparator<ListNode>(){
            public int compare(ListNode l1, ListNode l2){
                return l1.val - l2.val;
            }
        });
        ListNode res = new ListNode(0);
        ListNode tmp = res;
        int index = 0;
        // 将排序后的节点连接起来
        while(index < all.size()){
            tmp.next = all.get(index);
            tmp = tmp.next;
            index++;
        }
        return res.next;
    }
}

时间复杂度： $O (n l o g n)$ ，首先需要遍历所有的节点时间花费n，在使用collections.sort()进行排序需要nlogn的时间，整体时间复杂度为 $O (n l o g n)$ ；

空间复杂度： $O (1)$ ，都是在原有的节点上进行的修改，只需要常数级的引用变量。

方法2：每次对k个链表节点排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() == 0) return null;
        ListNode head = new ListNode(0);
        // 各数字位代表的值，主要用来求最值
        ArrayList<Integer> number = new ArrayList<>();
        ArrayList<ListNode> tests = new ArrayList<>(lists);
        for(ListNode tmp:lists){
            // 保证不为空，才会有下面的比较
            if(tmp != null){
                number.add(tmp.val);
            }else{
                tests.remove(tmp);
            }
        }
        ListNode res = head;
        while(!tests.isEmpty() && !number.isEmpty()){
            //求各链表中的最小值，放入res中
            int min = Collections.min(number);
            // 定位已经放入一个值的链表的位置
            int lindex = number.indexOf(Integer.valueOf(min));
            // 找到该链表
            ListNode ltmp = tests.get(lindex);
            // 若该节点为该链表的尾节点，则直接删掉
            if(ltmp.next == null){
                tests.remove(lindex);
                number.remove(lindex);
            } else {
                // 否则，替换为下一个节点
                tests.set(lindex, ltmp.next);
                number.set(lindex, ltmp.next.val);
            }
            res.next = new ListNode(min);
            res = res.next;
        }
        return head.next;
    }
}

时间复杂度： $O (n l o g k)$ ，n是链表的所有节点数，k是链表数，首先需要遍历所有的节点，但每次只需要在k个节点中获取最小的节点，时间复杂度logn，整体时间复杂度为 $O (n l o g k)$ ；

空间复杂度： $O (n)$ ，每次在获取了最小值后，都需要创建一个新的节点，需要使用额外的n空间。

题解 | NC51 #合并k个已排序的链表#

题目描述

题目分析

解题思路

代码实现