好久没刷题了，这个困难的题目，果然还是需要对链表的特性有一定的熟悉才好入手。
也是卡了好久，记录一下题解大大的做法，后面会再二刷、三刷，一定要摸清这些题目的规律
题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
思路
方法一：
hmm,不用过脑子的话，先想到的是将每个链表内容都塞入数组，排序后再转链表返回。
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
listArray = []
for singleNode in lists:
while singleNode:
listArray.append(singleNode.val)
singleNode = singleNode.next
resNode = temNode = ListNode(0)
listArray.sort(reverse=False) #sort 排序，false 从小到大
for temp in listArray:
temNode.next = ListNode(temp)
temNode = temNode.next
return resNode.next
执行用时：80 ms, 在所有 Python 提交中击败了86.79%的用户
内存消耗：21.6 MB, 在所有 Python 提交中击败了23.45%的用户
还有一个同样的思路是转dic，用key、value的形式去存链表，通过dic.keys 返回list再用sort排序，最后再转化整个链表。
方法二：
分治，摘自题解大大的一个图片。
分治的思想就是各自以中间点为分割比较，直至一方不存在，再合并到另一个链表。
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
length = len(lists)
# 边界情况
if length == 0:
return None
if length == 1:
return lists[0]
# 分治
mid = length / 2
return self.merge(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:length]))
def merge(self, node_a, node_b):
dummy = ListNode(None)
cursor_a, cursor_b, cursor_res = node_a, node_b, dummy
while cursor_a and cursor_b: # 对两个节点的 val 进行判断，直到一方的 next 为空
if cursor_a.val <= cursor_b.val:
cursor_res.next = ListNode(cursor_a.val)
cursor_a = cursor_a.next
else:
cursor_res.next = ListNode(cursor_b.val)
cursor_b = cursor_b.next
cursor_res = cursor_res.next
# 有一方的next的为空，就没有比较的必要了，直接把不空的一边加入到结果的 next 上
if cursor_a:
cursor_res.next = cursor_a
if cursor_b:
cursor_res.next = cursor_b
return dummy.next
方法三：
还有一个类似方法一的做法，就是通过python的一个库-->heapq来实现push和pop操作，其中弹出的元素为堆中最小的element
heappush(heap, item) # pushes a new item on the heap
item = heappop(heap) # pops the smallest item from the heap
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists or len(lists) == 0:
return None
import heapq
heap = []
# 首先 for 嵌套 while 就是将所有元素都取出放入堆中
for node in lists:
while node:
heapq.heappush(heap, node.val)
node = node.next
dummy = ListNode(None)
cur = dummy
# 依次将堆中的元素取出(因为是小顶堆，所以每次出来的都是目前堆中值最小的元素），然后重新构建一个列表返回
while heap:
temp_node = ListNode(heappop(heap))
cur.next = temp_node
cur = temp_node
print(heap)
return dummy.next