题目要求
(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 = Noneclass Solution(object):# @ 两两合并def merge2lists(self, l1, l2):dummy = tail = ListNode(0)while l1 and l2:if l1.val < l2.val:tail.next = l1l1 = l1.nextelse:tail.next = l2l2 = l2.nexttail = tail.nexttail.next = l1 or l2return dummy.nextdef mergeKLists(self, lists):""":type lists: List[ListNode]:rtype: ListNode"""if not lists:return Nonestart = 0end = len(lists) - 1mid = start + (end-start)/2# 划分过程到mid+1if 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 Noneall = [] # 首先获取所有链表节点的值for node in lists:while node:all.append(node.val)node = node.nextall.sort() # 对所有值进行排序dummy=tail=ListNode(0)for j in range(len(all)): # 根据拍好顺序的值生成新的链表tail.next = ListNode(all[j])tail = tail.nextreturn dummy.next