原题

合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。

样例
给出3个排序链表[2->4->null, null, -1->null]，返回 -1->2->4->null

解题思路

• 方法一：两两合并，最终合并成一个linked list，返回结果
• 相当于8->4->2->1, 一共logk层，每层都是n个节点(n表示k个链表的节点总和)，所以时间复杂度是O(nlogk)
• 实现上可以采用递归，divide and conquer的思想把合并k个链表分成两个合并k/2个链表的任务，一直划分，知道任务中只剩一个链表或者两个链表。
• 也可以采用非递归的方式
• 方法二：维护一个k个大小的min heap
• 每次取出最小的数O(1)，并且插入一个新的数O(logk)，一共操作n次，所以时间复杂度是O(nlogk)
• 如果不使用min heap，而是通过for循环每次找到最小，一次操作是O(k)，所以总的时间复杂度是O(nk)

完整代码

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

# 方法一 递归
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if lists == [] or lists == [[]]:
            return None
        return self.helper(lists)
    
    def helper(self, lists):
        if len(lists) <= 1:
            return lists[0]
        left = self.helper(lists[:len(lists) / 2])
        right = self.helper(lists[len(lists) / 2:])
        return self.merge(left, right)
        
    def merge(self, head1, head2):
        dummy = ListNode(0)
        tail = dummy
        while head1 and head2:
            if head1.val < head2.val:
                tail.next = head1
                head1 = head1.next
            else:
                tail.next = head2
                head2 = head2.next
            tail = tail.next
        if head1:
            tail.next = head1
        if head2:
            tail.next = head2
        return dummy.next

# 方法二 非递归
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        
        while len(lists) > 1:
            new_lists = []
            for i in range(0, len(lists) - 1, 2):
                merge_list = self.merge(lists[i], lists[i + 1])
                new_lists.append(merge_list)
            if len(lists) % 2 == 1:
                new_lists.append(lists[len(lists) - 1])
                
            lists = new_lists
        return lists[0]
        
    def merge(self, head1, head2):
        dummy = ListNode(0)
        tail = dummy
        while head1 and head2:
            if head1.val < head2.val:
                tail.next = head1
                head1 = head1.next
            else:
                tail.next = head2
                head2 = head2.next
            tail = tail.next
        if head1:
            tail.next = head1
        if head2:
            tail.next = head2
        return dummy.next
        
# 方法三 k个数的min heap
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            if node: 
                heap.append((node.val, node))
        heapq.heapify(heap)
        head = ListNode(0)
        curr = head
        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))
        return head.next