[leetcode刷题笔记]链表的分治操作

分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。在刷题时，发现在链表操作中，分治的思想也很常用，因此记录下来并作整理。

合并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)。

Reference

分治算法详解（超详细）