1. 23.合并多个有序链表

与归并排序思想一致，两两合并。

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
        if lists.count == 0 {
            return nil
        }
        return dfsMerge(lists, 0, lists.count-1)
    }
    
    func dfsMerge(_ lists: [ListNode?],_ start:Int,_ end:Int) -> ListNode? {
        if start == end {
            return lists[start]
        }
        let mid = (start+end)>>1
        let h1 = dfsMerge(lists, start, mid)
        let h2 = dfsMerge(lists, mid+1, end)
        
        return mergeTwoLists(h1, h2)
    }
    
    func mergeTwoLists(_ h1:ListNode?,_ h2:ListNode?) -> ListNode?{
        let h = ListNode.init(0)
        var tail:ListNode? = h
        
        var cur1 = h1
        var cur2 = h2
        
        while cur1 != nil && cur2 != nil {
            if cur1!.val<=cur2!.val {
                tail?.next = cur1
                tail = cur1
                cur1 = cur1?.next
            }else{
                tail?.next = cur2
                tail = cur2
                cur2 = cur2?.next
            }
        }
        
        var cur = cur1 != nil ?cur1:cur2
        while cur != nil {
            tail?.next = cur
            tail = cur
            cur = cur?.next
        }
        
        return h.next
    }

2. 148. 排序链表

思路:与归并思想一致

1. 快慢指针查找中点
2. 分别递归，然后合并

func sortList(_ head: ListNode?) -> ListNode? {
        if head == nil {
            return nil
        }
        return dfsSortList(head)
    }
    
    func dfsSortList(_ head:ListNode?) -> ListNode? {
        if head?.next == nil {//递归条件
            return head
        }
        let mid = findMid(head)
        let next = mid?.next
        mid?.next = nil
        
        let l = dfsSortList(head)
        let r = dfsSortList(next)
        return mergeSortList(l,r)
    }
    
    func mergeSortList(_ h1: ListNode?,_ h2: ListNode?) -> ListNode? {
        let newHead:ListNode = ListNode.init(-1)
        var tail = newHead
        
        var cur1 = h1
        var cur2 = h2
        var next1 = cur1?.next
        var next2 = cur2?.next
        
        while cur1 != nil && cur2 != nil {
            if cur1!.val <= cur2!.val{
                tail.next = cur1
                tail = cur1!
                
                cur1 = next1
                next1 = cur1?.next
            }else{
                tail.next = cur2
                tail = cur2!
                
                cur2 = next2
                next2 = cur2?.next
            }
        }
        
        var cur = cur1 != nil ?cur1:cur2
        while cur != nil {
            tail.next = cur
            tail = cur!
            cur = cur?.next
        }
        
        return newHead.next
    }
    
    func findMid(_ head:ListNode?) -> ListNode? {
        var slow = head
        var fast = head?.next
        
        while fast != nil && fast?.next != nil{
            slow = slow?.next
            fast = fast?.next?.next
        }
        
        return slow
    }