# [leetcode题解]23.Merge K Sorted Lists(多链表合并)

leetcode,23题，Merge K Sorted Lists,多排序链表合并为一个有序链表问题。可以直接使用priority_queue或者heap。

c++题解：

```class cmp
{
public:
bool operator()(ListNode *pa, ListNode *pb)
{
return pa->val > pb->val;
}
};

class Solution {
//author：凌风技术站-iaccepted
public:
ListNode* mergeKLists(vector<ListNode*>& lists)
{
//去除空链表
for (auto ite = lists.begin(); ite != lists.end();)
{
if (*ite == NULL)ite = lists.erase(ite);
else ++ite;
}

priority_queue<ListNode *, vector<ListNode *>, \
cmp> pq(lists.begin(), lists.end());

ListNode *pre = new ListNode(-1);
ListNode *tail = pre;

//合并为一个链表
while(!pq.empty())
{
ListNode *top = pq.top();
pq.pop();
tail->next = top;
tail = tail->next;

if (top->next != NULL)
{
pq.push(top->next);
}
}
tail->next = NULL;
return pre->next;
}
};
```

python题解：

```from Queue import PriorityQueue

class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
:author: 凌风技术站-iaccepted
"""
pq = PriorityQueue()
for item in lists:
if item is not None:
pq.put((item.val, item))

pre = ListNode(-1)
tail = pre
while not pq.empty():
top = pq.get()
tail.next = top[1]
tail = tail.next

l = top[1].next
if l is not None:
pq.put((l.val, l))
tail.next = None
return pre.next```