112 lines
2.5 KiB
Markdown
112 lines
2.5 KiB
Markdown
# 合并 K 个升序链表
|
||
|
||
## 题目
|
||
|
||
给你一个链表数组，每个链表都已经按升序排列。
|
||
|
||
请你将所有链表合并到一个升序链表中，返回合并后的链表。
|
||
|
||
|
||
示例 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 = [[]]
|
||
输出：[]
|
||
|
||
|
||
提示：
|
||
|
||
k == lists.length
|
||
0 <= k <= 10^4
|
||
0 <= lists[i].length <= 500
|
||
-10^4 <= lists[i][j] <= 10^4
|
||
lists[i] 按 升序 排列
|
||
lists[i].length 的总和不超过 10^4
|
||
|
||
## 思路
|
||
|
||
- 分冶
|
||
|
||
## 代码
|
||
|
||
```java
|
||
/**
|
||
* Definition for singly-linked list.
|
||
* public class ListNode {
|
||
* int val;
|
||
* ListNode next;
|
||
* ListNode() {}
|
||
* ListNode(int val) { this.val = val; }
|
||
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
|
||
* }
|
||
*/
|
||
class Solution {
|
||
public ListNode mergeKLists(ListNode[] lists) {
|
||
// Special
|
||
if (lists == null || lists.length == 0) {
|
||
return null;
|
||
}
|
||
// Init: To List
|
||
List<ListNode> nlists = new ArrayList<>(Arrays.asList(lists));
|
||
while (nlists.size() > 1) {
|
||
// Traverse: l1 + l2 = list
|
||
List<ListNode> tempList = new ArrayList<>();
|
||
for (int i = 0; i < nlists.size(); i+=2) {
|
||
// Get l1, l2
|
||
ListNode l1 = nlists.get(i);
|
||
ListNode l2 = null;
|
||
if (i + 1 < nlists.size()) {
|
||
l2 = nlists.get(i + 1);
|
||
}
|
||
// Merge
|
||
tempList.add(mergeTwoLists(l1, l2));
|
||
}
|
||
nlists = tempList;
|
||
}
|
||
|
||
return nlists.get(0);
|
||
|
||
}
|
||
|
||
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
|
||
// Init: DummyHead, cur
|
||
ListNode dummyHead = new ListNode(-1);
|
||
ListNode cur = dummyHead;
|
||
// Traverse: Compare
|
||
while (list1 != null && list2 != null) {
|
||
// val1 = list1.val;
|
||
// val2 = list2.val;
|
||
ListNode tmp = null;
|
||
if (list1.val > list2.val) {
|
||
tmp = list2;
|
||
list2 = list2.next;
|
||
} else {
|
||
tmp = list1;
|
||
list1 = list1.next;
|
||
}
|
||
cur.next = tmp;
|
||
cur = cur.next;
|
||
}
|
||
|
||
cur.next = list1 == null ? list2 : list1;
|
||
|
||
return dummyHead.next;
|
||
|
||
}
|
||
}
|
||
``` |