每日题解:LeetCode 23. 合并K个排序链表

题目地址 个人博客地址

题目描述

合并 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)); } 第一轮拆分成k/2，第二轮拆分成k/4，然后为k/8直到不能拆分，即left=right,然后合并每对的链表，从k/8合并到k/4.，k/4合并到k/2，重复拆，然后合并的过程，直到得到最终的有序链表 庆贺自己又完成一个月的打卡