分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在刷题时，发现在链表操作中，分治的思想也很常用，因此记录下来并作整理。
合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 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 None
return self.merge(lists, 0, len(lists) - 1)
def merge(self,lists: List[ListNode],l:int,r:int) ->List[ListNode]:
if l == r:
return lists[l]
if l > r:
return None
mid = (l + r) //2
return self.mergeTwoLists(self.merge(lists,l,mid),self.merge(lists,mid+1,r))
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
p,q = l1,l2
m = ListNode(-1)
n = m
while p and q:
if p.val <= q.val:
m.next = p
p = p.next
else:
m.next = q
q = q.next
m = m.next
if not p:
m.next = q
if not q:
m.next = p
return n.next
排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例:
输入: 4->2->1->3
输出: 1->2->3->4
使用分治的思想解题，即需要找到mid节点将链表分开，然后分而治之最后合并。
class Solution:
def sortList(self, head: ListNode) -> ListNode:
#归并排序--递归
if not head or not head.next:
return head
mid = self.getMid(head)
left = self.sortList(head)
right = self.sortList(mid)
return self.mergeTwoLists(left,right) #mergeTwoLists与上题相同
def getMid(self,head):
if not head or not head.next:
return head
pre = head
slow = head.next
fast = head.next
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
return slow
由于使用 归并排序，时间复杂度O(n log n)，快速排序 也是采用了分治的思想，在理想的情况，每次划分所选择的中间数恰好将当前序列几乎等分，经过log n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog n)。若在每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)。
