# 刷题之合并K个排序链表

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

#### 思路三（推荐）

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
nodeList = []
for i in range(len(lists)):
currentNode = lists[i]
while currentNode:
nodeList.append(currentNode)
currentNode = currentNode.next

nodeList = sorted(nodeList, key=lambda x: x.val)

for i in range(len(nodeList)):
currentNode.next = nodeList[i]
currentNode = currentNode.next

#### 思路四

```# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
heap = []
for node in lists:
if node != None:
heap.append((node.val, node))
heapq.heapify(heap)
while heap:
pop = heapq.heappop(heap)
curr.next = ListNode(pop[0])
curr = curr.next
if pop[1].next:
heapq.heappush(heap, (pop[1].next.val, pop[1].next))

125 篇文章66 人订阅

0 条评论