原題

合并k個排序鏈表，并且返回合并后的排序鏈表憾朴。嘗試分析和描述其復(fù)雜度狸捕。

樣例
給出3個排序鏈表[2->4->null, null, -1->null]，返回 -1->2->4->null

解題思路

• 方法一：兩兩合并众雷，最終合并成一個linked list灸拍，返回結(jié)果
• 相當(dāng)于8->4->2->1, 一共logk層做祝，每層都是n個節(jié)點(diǎn)(n表示k個鏈表的節(jié)點(diǎn)總和)，所以時間復(fù)雜度是O(nlogk)
• 實現(xiàn)上可以采用遞歸鸡岗，divide and conquer的思想把合并k個鏈表分成兩個合并k/2個鏈表的任務(wù)混槐，一直劃分，知道任務(wù)中只剩一個鏈表或者兩個鏈表轩性。
• 也可以采用非遞歸的方式
• 方法二：維護(hù)一個k個大小的min heap
• 每次取出最小的數(shù)O(1)声登，并且插入一個新的數(shù)O(logk)，一共操作n次揣苏，所以時間復(fù)雜度是O(nlogk)
• 如果不使用min heap悯嗓，而是通過for循環(huán)每次找到最小，一次操作是O(k)卸察，所以總的時間復(fù)雜度是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個數(shù)的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