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/