leetcode 23 Merge k Sorted Lists（合并k个排序链表）

题目要求

(hard) 合并k个已排序的链表并将其作为一个排序列表返回。 分析并描述其复杂性。

解题思路

这道题是基于合并两个解答leetcode 21 Merge Two Sorted Lists （合并两个有序链表）二来，我们通过这个思想可以把K个链表递归的分成两个两个一组，也就是我们说的分治法，然后依次向上合并，这样的解法也是比较高效的。主要过程为两个：

（1）递归的划分每个链表到左部分或右部分，类似二分法，需要注意的是如果划分只剩一个链表了，说明已经划分完毕了。

（2）合并划分好的链表，直接傀儡节点套用 解答leetcode 21 Merge Two Sorted Lists （合并两个有序链表）即可。

特别的，还说一种思路，就是把K个链表中所有节点的值都存下来，然后排序，之后再根据排序好的值进行建链表的过程，这个方法非常好理解，就是时间消耗比较多，当节点数很多的时候，效率不是很好。所以还是主要推荐分治法，当然还有一些最小堆等方法，大家可以自己上网再看看，以后我再给补上。

主要代码python

分治法 （O(nlogk)）强推！！

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

class Solution(object):
	# @ 两两合并
   def merge2lists(self, l1, l2):
	   dummy = tail = ListNode(0)
	      while l1 and l2:
	          if l1.val < l2.val:
	              tail.next = l1
	              l1 = l1.next
	          else:
	              tail.next = l2
	              l2 = l2.next
	          tail = tail.next
	      tail.next = l1 or l2
	      return dummy.next
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        start = 0
        end = len(lists) - 1
        mid = start + (end-start)/2
        # 划分过程到mid+1
        if len(lists)>2:
            p1 = self.mergeKLists(lists[:mid+1])
            p2 = self.mergeKLists(lists[mid+1:])
        elif len(lists)==2:
            p1 = lists[0]
            p2 = lists[1]
        else:
            return lists[0] # 到底了
        return self.merge2lists(p1,p2)
           

排序法O(nlogn)

# 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 is None:
            return None
        all = [] # 首先获取所有链表节点的值
        for node in lists:
            while node:
                all.append(node.val)
                node = node.next
        all.sort() # 对所有值进行排序
        dummy=tail=ListNode(0)
        for j in range(len(all)): # 根据拍好顺序的值生成新的链表
            tail.next = ListNode(all[j])
            tail = tail.next
        return dummy.next
           

原题链接 https://leetcode.com/problems/merge-k-sorted-lists/submissions/