一、题目
1、算法题目
“将链表数组合并到一个升序链表中。”
题目链接：
来源：力扣（LeetCode）
链接：23. 合并K个升序链表 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]] 输出： [] 复制代码
二、解题
1、思路分析
这个题可以采用分治和递归的思路进行解决。
首先是分治，将k个链表分成k/2个链表组，两两合并，直到合并成一个链表。
然后用递归实现分治算法。
2、代码实现
代码参考：
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode MergeKLists(ListNode[] lists) { if(lists == null || lists.Length == 0) { return null; } return MergeKLists(lists, 0, lists.Length-1); } private ListNode MergeKLists(ListNode[] lists, int left, int right) { if(left == right) { return lists[left]; } int mid = left + (right-left)/2; ListNode l1 = MergeKLists(lists, left, mid); ListNode l2 = MergeKLists(lists, mid+1, right); return MergeTwoLists(l1, l2); } private ListNode MergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) { return l2; } if(l2 == null) { return l1; } ListNode dummy = new ListNode(); ListNode p1 = l1, p2 = l2, cur = dummy; while(p1 != null && p2 != null) { if(p1.val < p2.val) { cur.next = p1; cur = cur.next; p1 = p1.next; } else { cur.next = p2; cur = cur.next; p2 = p2.next; } } cur.next = p1 == null ? p2 : p1; return dummy.next; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n∗k∗logk)
其中链表数组长度为 k，链表的平均长度为 n。函数 MergeKLists 的时间复杂度为 O(k logk)（分治），函数 MergeTwoLists 的时间复杂度是 O(n)，因此总的时间复杂度为 O(n∗k∗logk)。
空间复杂度： O(logk)
递归会使用到 O(logk) 空间代价的栈空间。
三、总结
结束条件：left == right，即只剩下一个链表，无须合并，直接返回。
