一、题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
二、解题思路
分治思想
- 将大问题划分为两个到多个子问题
- 子问题可以继续拆分成更小的子问题，直到能够简单求解
- 如有必要，将子问题的解进行合并，得到原始问题的解
分而治之，分到区间内只有一个链表，合并区间；所以问题就转化为了合并两个有序链表。
2.1 合并两个有序链表
leetcode21.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路
递归函数返回
- 更小的那个链表节点，并把它剩余节点与另一个链表再次递归
- 返回之前更新此节点的 next（原本的next需要更新为归回来的那个更小的链表节点）
代码实现
/**
* Leetcode21: 合并两个有序链表【递归】
* @param list1
* @param list2
* @return
*/
public static ListNode mergeTwoSortedListsRecursion(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
ListNode listNode = mergeTwoSortedListsRecursion(list1.next, list2);
list1.next = listNode;
return list1;
} else {
ListNode listNode = mergeTwoSortedListsRecursion(list1, list2.next);
list2.next = listNode;
return list2;
}
}
递归执行流程
递归合并两个有序链表.png
2.2 把k个链表依次拆解
/**
* 合并k个升序链表
* @param lists
* @return
*/
public static ListNode mergeKListsRecursion(ListNode[] lists) {
if (lists == null) {
return null;
}
return split(lists, 0, lists.length - 1);
}
/**
* 把k个链表依次拆解，拆到只剩下一个，两两合并
* @param lists
* @param i
* @param j
* @return
*/
public static ListNode split(ListNode[] lists,int i,int j) {
// 拆到数组中只剩下一个元素时终止递归 此时i和j重合
if (i == j) {
return lists[i];
}
int mid = (i+j) >>> 1;
ListNode left = split(lists, i, mid);
ListNode right = split(lists, mid+1, j);
//合并后的链表
ListNode listNode = mergeTwoSortedListsRecursion(left, right);
return listNode;
}
拆解链表递归执行流程
链表拆分递归流程.png
