【算法面试必刷Java版五】合并k个已排序的链表

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：合并k个已排序的链表

描述：

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围：节点总数满足 0≤n≤105，链表个数满足 1≤k≤105 ，每个链表的长度满足 1≤len≤200 ，每个节点的值满足 |val| <=1000

要求：时间复杂度 O(nlogk)

思路：

两个有序链表合并，我们可以使用上一题中合并链表的方法：准备双指针分别放在两个链表头，每次取出较小的一个元素加入新的大链表，将其指针后移，继续比较，这样我们出去的都是最小的元素，自然就完成了排序。

继续上面的思路，我们可以取开头的两个链表合并，然后得到新链表继续合并，直到只剩一个链表，可是这种方式想一下也很浪费时间，因为第一个链表会变的明显大于其他链表，不够均衡。

所以我们可以使用分治的思想，我们只需要将两两合并，然后将合并后的新链表继续两两合并。

代码：

public static void main(String[] args) {
    ListNode listNode1 = new ListNode(1);
    ListNode listNode2 = new ListNode(3);
    ListNode listNode3 = new ListNode(5);
    ListNode listNode4 = new ListNode(2);
    ListNode listNode5 = new ListNode(4);
    ListNode listNode6 = new ListNode(6);
    ListNode listNode7 = new ListNode(7);
    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = null;
    listNode4.next = listNode5;
    listNode5.next = null;
    listNode6.next = listNode7;
    listNode7.next = null;
    ArrayList<ListNode> lists = new ArrayList<>();
    lists.add(listNode1);
    lists.add(listNode4);
    lists.add(listNode6);
    ListNode result = mergeKLists(lists);
    while (result!=null){
        System.out.println(result.val);
        result = result.next;
    }
}

public static ListNode mergeKLists(ArrayList<ListNode> lists) {
    while (lists.size()>1){
        ListNode listNode1 = lists.remove(0);
        ListNode listNode2 = lists.remove(0);
        lists.add(Merge(listNode1,listNode2));
    }
    if (lists.size()==1){
        return lists.get(0);
    }else {
        return null;
    }
}

public static ListNode Merge(ListNode list1, ListNode list2) {
    ListNode pre = new ListNode(-1);
    ListNode cur = pre;
    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        }else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    if (list1!=null){
        cur.next = list1;
    }else {
        cur.next = list2;
    }
    return pre.next;
}

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101