23. Merge k Sorted Lists

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

传送门

分治法实现

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeKLists(self, lists: List[ListNode]) -> ListNode: if not lists: return return self._mergeKLists(lists,0,len(lists)-1) def _mergeKLists(self,lists,left,right): if left==right: return lists[left] mid= left+(right-left)//2 listNode1=self._mergeKLists(lists,left,mid) listNode2=self._mergeKLists(lists,mid+1,right) return self.mergeTwoLists(listNode1,listNode2) def mergeTwoLists(self, l1, l2) : if not l1: return l2 if not l2: return l1 if l1.val<=l2.val: l1.next=self.mergeTwoLists(l1.next,l2) return l1 else: l2.next=self.mergeTwoLists(l1,l2.next) return l2 # def mergeTwoLists(self, l1, l2) : # prehead=ListNode(-1) # prev=prehead # # prev与prehead 指向同一个None # while l1 and l2: # if l1.val<=l2.val: # prev.next=l1 # l1=l1.next # prev=prev.next # else: # prev.next=l2 # l2=l2.next # prev=prev.next # prev.next=l2 if not l1 else l1 # return prehead.next

算法复杂度分析

归并思想，每一次使得子问题的大小变为一半，即呈指数级下降 这里的链表个数为$K$,所有的元素数量为$N$,完成$K$个链表合并的时间复杂度定义为$O(K)$ $$\begin{gathered} O\left(K\right)=2O\left(\frac{K}{2}\right)+O\left(N\right) \\ =O\left(Nlo{g}_{2}K\right) \end{gathered}$$ 这里为方便我假设每$K/2$个链表含有的元素是相等的，即为$N/2$,则合并两个长度为$\frac{N}{2}$链表复杂度为$O(N)$,这里可以参考21 题合并两个链表