题目地址
个人博客地址

题目描述

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

示例:

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

解法

CPP

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       return merge(lists,0,lists.size()-1);
    }
    ListNode* merge(vector<ListNode*>& lists,int left, int right) {
        if(left==right){
            return  lists[left];
        }
        if (left > right) return nullptr;
        int mid = (left + right) >> 1;
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

    ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *prehead = new ListNode(-1);
        ListNode *prev = prehead;
        while (l1 && l2){
            if(l1->val<=l2->val){
                prev->next=l1;
                l1=l1->next;
            }else {
                prev->next=l2;
                l2=l2->next;
            }
            prev= prev->next;
        }
        prev->next=l1?l1:l2;
        return  prehead->next;
    }
};

解题思路

分治合并

这题需要完成前置的一题合并两个有序链表，组合刷题，建立两题一起刷
JAVA写法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode prehead = new ListNode(-1);
       ListNode prev = prehead;
        while (l1!=null && l2!=null){
            if(l1.val<=l2.val){
                prev.next=l1;
                l1=l1.next;
            }else {
                prev.next=l2;
                l2=l2.next;
            }
            prev= prev.next;
        }
        prev.next=l1==null?l2:l1;
        return  prehead.next;

    }
}

合并两个有序链表采用了递归的写法，思路就是对比两个链表的当前值，然后prev 指向当前值小的节点，由于链表是已升序排序，其中一个链表合并完，后面就直接指向未遍历完的链表即可
回到今天需要解答的题目：合并K个排序链表

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

以上是来自百度关于分治算法的解释，题目要求合并K个排序链表，那就按照分治算法的思路，把链表集合分成多个链表范围进行合并，如图

将合并K个排序链表分成多个合并两个有序链表，

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        merge(lists,0,lists.size()-1);
    }
    ListNode* merge(vector<ListNode*>& lists,int left, int right) {
        if(left==right){
            return  lists[left];
        }
        if (left > right) return nullptr;
        int mid = (left + right) >> 1;
        //将集合拆分成左右两份，最后在合并
        return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
    }

1. 第一轮拆分成k/2，第二轮拆分成k/4，然后为k/8直到不能拆分，即left=right,
2. 然后合并每对的链表，从k/8合并到k/4.，k/4合并到k/2，重复拆，然后合并的过程，直到得到最终的有序链表