[LeetCode] 23. Merge k Sorted Lists 合并K个元素的有序链表 @python

Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

---

合并含有K个元素的有序链表，并且作为一个有序链表的形式返回。分析并描述它的复杂度。

---

Solution

本题可以使用最小堆结构进行代码实现。
首先将每个list里面的第一个元素，也就是每个list的最小元素（因为list都是已排序），共K个指放入大小为K的堆中，将其维护成最小堆结构。每次将堆顶的元素，也就是最小元素放到结果中，然后取出该元素原先所处的list中的下一个元素放入队中，维护最小堆结构。当所有元素读取完，所有的元素就按照从小到大放到结果链表中。

在本次实现中直接使用了Python提供的最小堆的结构。

heapq使用说明
a为普通列表 
- heapq.heapify(a) 调整a，使得其满足最小堆 
- heapq.heappop(a) 从最小堆中弹出最小的元素 
- heapq.heappush(a,b) 向最小堆中压入新的元素

---

# -*- coding: utf-8 -*-
""" Created on Sat Mar 17 18:01:37 2018 @author: Saul """

# 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 """

        heap = []
        for ln in lists:
            if ln:
                heap.append((ln.val, ln))
        dummy = ListNode(0)
        cur = dummy
        heapq.heapify(heap)
        while heap:
            valu, ln_index = heapq.heappop(heap)
            cur.next = ln_index
            cur = cur.next
            if ln_index.next:
                heapq.heappush(heap, (ln_index.next.val, ln_index.next))
        return dummy.next