日期：20180913

题目描述：

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

详解：

Approach: Merge with Divide And Conquer

Intuition & Algorithm

This approach walks alongside the one above but is improved a lot. We don't need to traverse most nodes many times repeatedly

• Pair up k lists and merge each pair.
• After the first pairing,k lists are merged into k/2 lists with average 2N/k length, then k/4, k/8 and so on.
• Repeat this procedure until we get the final sorted linked list.

Thus, we'll traverse almost N nodes per pairing and merging, and repeat this procedure about log2k times.

Divide_and_Conquer

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0] if amount > 0 else lists

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next
        if not l1:
            point.next=l2
        else:
            point.next=l1
        return head.next

整体思路是先合并两个链表，然后对于k个链表两两合并。合并两个链表，可以用递归，也可以想上面的代码一样采用牺牲头结点的方法，之前已经讲过构造链表牺牲头结点的方法了，这里不再赘述。

有的时候写循环体里面还有判断的时候会把自己绕糊涂，我有一个笨方法不过挺管用，就是现在草纸上把代码一行一行写出来，不用循环体，手动模拟循环的过程，最后看哪几行代码从何处开始重复，就把代码结构捋清了。不知道这么笨的方法是不是只有我一个人用。。。。