## 开胃菜

### 题目 21. 合并两个有序链表

输入：1->2->4, 1->3->4



### 思路

• java 实现
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
List<Integer> numsOne = getIntegerList(l1);
List<Integer> numsTwo = getIntegerList(l2);
Collections.sort(numsOne);
// 构建结果
}

private List<Integer> getIntegerList(ListNode oneNode) {
while (oneNode != null) {
int value = oneNode.val;
oneNode = oneNode.next;
}
return resultList;
}
if(integers.size() == 0) {
return null;
}
for(int i = 1; i < integers.size(); i++) {
temp.next = new ListNode(integers.get(i));
temp = temp.next;
}
}


### 效果

Runtime: 4 ms, faster than 22.43% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 39.6 MB, less than 19.99% of Java online submissions for Merge Two Sorted Lists.


### 实现

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
}
if(l2 == null) {
return l1;
}
// 临时变量
ListNode newNode = new ListNode(0);
// 新增的头指针
// 循环处理
while (l1 != null && l2 != null) {
int valOne = l1.val;
int valTwo = l2.val;
// 插入小的元素节点
if(valOne <= valTwo) {
newNode.next = l1;
l1 = l1.next;
} else {
newNode.next = l2;
l2 = l2.next;
}
// 变换 newNode
newNode = newNode.next;
}
// 如果长度不一样
if(l1 != null) {
newNode.next = l1;
}
if(l2 != null) {
newNode.next = l2;
}
}


### 效果

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Two Sorted Lists.
Memory Usage: 38.8 MB, less than 88.76% of Java online submissions for Merge Two Sorted Lists.


## 进阶版

1. 合并K个排序链表

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



## 1. 暴力破万法

### 思路

• java 实现

public ListNode mergeKLists(ListNode[] lists) {
if(null == lists || lists.length == 0) {
return null;
}
// 查找操作比较少
for(ListNode listNode : lists) {
}
// 排序
Collections.sort(integerList);
// 构建结果
}

private List<Integer> getIntegerList(ListNode oneNode) {
while (oneNode != null) {
int value = oneNode.val;
oneNode = oneNode.next;
}
return resultList;
}

if(integers.size() == 0) {
return null;
}
for(int i = 1; i < integers.size(); i++) {
temp.next = new ListNode(integers.get(i));
temp = temp.next;
}
}


### 效果

Runtime: 103 ms, faster than 15.12% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 40.6 MB, less than 94.79% of Java online submissions for Merge k Sorted Lists.


## 2. k = (k-1) + 1

### 实现

public ListNode mergeKLists(ListNode[] lists) {
if(null == lists || lists.length == 0) {
return null;
}
//
ListNode result = lists[0];
// 从第二个开始遍历
for(int i = 1; i < lists.length; i++) {
ListNode node = lists[i];
result = mergeTwoLists(result, node);
}
return result;
}


mergeTwoLists 使我们在两个链表合并中的最佳解法，这里复用了一下。

### 效果

Runtime: 98 ms, faster than 16.31% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.4 MB, less than 47.50% of Java online submissions for Merge k Sorted Lists.


## 3. 优先级队列-排序我最强

### 实现

public ListNode mergeKLists(ListNode[] lists) {
if(null == lists || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
// 循环添加元素
for(ListNode listNode : lists) {
if(listNode != null) {
queue.offer(listNode);
}
}
// 依次弹出
}
/**
* 构建头节点
* @param queue 列表
* @return 结果
* @since v2
*/
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!queue.isEmpty()) {
tail.next = queue.poll();
tail = tail.next;
// 这里类似于将 queue 层层剥开放入 queue 中
if(tail.next != null) {
}
}
return dummy.next;
}


### 效果

Runtime: 4 ms, faster than 81.55% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.1 MB, less than 74.81% of Java online submissions for Merge k Sorted Lists.


4ms! 这次简直是质的飞跃，从 100ms 提升了 25 倍左右。可喜可贺。

## 4. 分治-分而治之，各个击破

• 思想

### 实现

public ListNode mergeKLists(ListNode[] lists) {
final int length = lists.length;
if(lists.length == 0) {
return null;
}
if(lists.length == 1) {
return lists[0];
}
// 递归获取两个节点
int mid = (length) / 2;
ListNode one = mergeKLists(subArray(lists, 0, mid));
ListNode two = mergeKLists(subArray(lists, mid, length));
// 合并最后2个节点
return mergeTwoLists(one, two);
}

private ListNode[] subArray(ListNode[] listNodes, int start, int end) {
int size = end-start;
ListNode[] result = new ListNode[size];
int index = 0;
for(int i = start; i < end; i++) {
result[index++] = listNodes[i];
}
return result;
}


### 效果

Runtime: 2 ms, faster than 91.66% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.5 MB, less than 34.83% of Java online submissions for Merge k Sorted Lists.


2ms! 我们又把速度提升了一倍，这下你满意了吗？

## 5. 优化的尽头

### 思路

[1, 2, 3, 4]


[(1,4), 2, 3]
[(1,4,3), 2]
[(1,4,3,2)]


### 实现

public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
int i = 0;
int j = lists.length - 1;
while (j > 0) {
// ?
i = 0;
while (i < j) {
lists[i] = mergeTwoLists(lists[i], lists[j]);
i++;
j--;
}
}
return lists[0];
}


### 效果

Runtime: 1 ms, faster than 100.00% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.5 MB, less than 35.98% of Java online submissions for Merge k Sorted Lists.


1ms! 我们将这个算法从 100ms 优化到 1ms。

leetcode 源码实现

# 开源地址

https://github.com/houbb/leetcode

## 参考资料

https://leetcode.com/problems/merge-k-sorted-lists/submissions/

https://leetcode-cn.com/problems/merge-two-sorted-lists