Merge K sorted Lists

这道题是链表类里面最难的题目了，而且很有参考价值，因为它有多种方法可以求解，首先是利用堆的性质求解，我们先把链表的头一个数压入堆中，然后每次弹出就把弹出点对应的链表往前推一格，如果没有节点了则加入sys.maxint，这样当heap的堆顶都是sys.maxint时循环完成，下面是代码

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        n = len(lists)
        for i in xrange(n):
            if lists[i]:
                heapq.heappush(heap, [lists[i].val, i])
            else:
                heapq.heappush(heap, [sys.maxint, i])

        dummy = ListNode('dum')
        cur = dummy
        while heap and heap[0][0] != sys.maxint:
            val, index = heapq.heappop(heap)
            cur.next = ListNode(val)
            cur = cur.next
            lists[index] = lists[index].next
            if lists[index]:
                heapq.heappush(heap, [lists[index].val, index])
            else:
                heapq.heappush(heap, [sys.maxint, index])

        return dummy.next

另外还有一种Divide and Conquer思路的做法也是很正常的，不过这里要注意的是，我们做的是先把数组平分两半，然后递归向下直到只有两个链表或只有一个链表时才进行合并，而合并的方法用的就是合并两条链表的算法，然后再回过头来回溯并合并更大规模的链表，下面是代码

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode('di')
        cur = dummy
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = ListNode(l1.val)
                l1 = l1.next
            else:
                cur.next = ListNode(l2.val)
                l2 = l2.next
            cur = cur.next

        cur.next = l1 if l1 else l2

        return dummy.next

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        return self.helper(lists, 0, len(lists) - 1)

    def helper(self, nums, start, end):
        if start >= end:
            return nums[end]

        if start + 1 == end:
            return self.mergeTwoLists(nums[start], nums[end])

        mid = start + (end - start) / 2
        left = self.helper(nums, start, mid)
        right = self.helper(nums, mid + 1, end)
        return self.mergeTwoLists(left, right)