23. 合并K个升序链表 👌

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]

比如说，给你以下 3 个有序链表：
1 -> 2 -> 4
1 -> 4 -> 8
0 -> 2
合并后的有序链表是：
0 -> 1 -> 1 -> 2 -> 2 -> 4 -> 4 -> 8

解题思路

知道合并两个有序链表的思路，那么合并k个有序链表最容易想到的方法就是，
遍历链表数组，使用合并两个有序链表的方法，一个个合并过去即可。
假设这k个链表的平均长度是m，也就是平均下来，一个链表有m个节点。
则合并的节点总数 n 就是,n = k*m。合并两个有序链表的时间复杂度是他们长度之后。
那合并两个有序链表的时间复杂度是O(2m)，和第三条链表合并即时间复杂度是O(3m)。
一共k个链表，即总的时间复杂度是O(2m)+O(3m)+…+O(km) = O((k+2)(k-1)/2_m) = O(k^2_m),
因此k_m=n,所以总的时间复杂度是O(k_n),n是所有链表的节点总数。
这种方法是不需要使用额外的存储空间。因此空间复杂度是O(1)
解法一：暴力？

//时间复杂度K^2N,结合合并两个有序链表，暴力法？
//函数1，时间K，空间1
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {    //lists,数组【】，只不过是多个链表组成的【a】【b】,a=ListNode.val
        return nil
    }
   var result *ListNode                 // 否则定义合并后的结果链表，两种遍历，方法1
   for _, list := range lists {         // 定义链表数组
        result = Merge(result, list)     // 和数组中的链表一个个合并,当前和所有
    }    
    return result
}
//迭代法 哨兵模式,复杂度On,O1
func merge(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    prev := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            prev.Next = l1
            l1 = l1.Next
        } else {
            prev.Next = l2
            l2 = l2.Next
        }
        prev = prev.Next
    }
    if l1 == nil {
        prev.Next = l2
    }
    if l2 == nil {
        prev.Next = l1
    }
    return dummy.Next
}

最优解法：

解题思路 - 分治算法~归并法

• 1、将lists拆分为两半，先合并前一半，再合并后一半
• 2、然后把得到的两条合并链表合并
• 3、在此过程中，原lists的前一半，又会继续拆分为1/4,1/8， 直到分拆的链表只剩下单个元素，返回自己就好了

像归并排序一样使用分治法处理，假如k个链表分别为a1, a2, a3,…, ak
不断递归直到只需要处理两个链表的合并，之后两两合并，得到b1, b2 , … , 新链表，
接着继续两两合并得到c1, c2,… 直到最后只剩下一条有序链表。
这个方法在每一层的合并中，都需要处理所有的n个节点，而每次处理后链表的数量变为原来的一半。
总共要处理logk次，总的时间复杂度是O(n*logk).
使用的辅助空间大小为递归调用的深度，总共有logk层，所以空间复杂度为O(logk)

//归并排序法，时间: kn*logk  空间:logk
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return  nil 
    }
    return merge(lists, 0, len(lists)-1)
}

func merge(lists []*ListNode, start, end int) *ListNode {
    if start == end {
        return lists[start]
    }

    mid := start + (end - start)/2
    left := merge(lists, start, mid)
    right := merge(lists, mid+1, end)

    return mergeTwoSortedLists(left, right)
}

func mergeTwoSortedLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    pre := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            pre.Next = l1
            l1 = l1.Next
        } else {
            pre.Next = l2
            l2 = l2.Next
        }
        pre = pre.Next
    }

    if l1 == nil {
        pre.Next = l2
    }
    if l2 == nil {
        pre.Next = l1
    }
    return dummy.Next
}

解题思路 - 最小堆

建堆太麻烦了，别写了

由于每个链表都是递增的，因此每次要拿的最小值都是在每个链表的头节点。
比如，上面3个有序链表第一个值应该在三个链表的头节点1，1，0中找最小值为0。
之后游标移动到 0 -> 2 节点0之后的节点2，然后要找1，1，2中的最小值。
使用这个方法依次取每个链表上的每一个节点，直到取完，就可以得到合并后的有序链表。
这种方法每一轮要对比k次。每一轮对比完可以确定一个节点，总共有n个节点。
因此时间复杂度是O(kn)，这里可以做一点优化，使用最小堆来维护当前k个值的关系。
这样每次只需要O(1)的时间取得当前k个值的最小值。
则新的节点加入到大小为k的堆，则需要O(logK)的时间去调整堆的结构。
这样每一轮操作只能确定一个节点的位置，因此总时间复杂度是O(nlogk),
使用了大小为k的辅助堆，因此空间复杂度是O(k)

// Time: O(n*log(k)), Space: O(k) n是总节点数量，k是链表个数
func mergeKLists2(lists []*ListNode) *ListNode {
   if lists == nil || len(lists) == 0 {
      return nil // 链表为空或长度为0，直接返回空指针
   }
   var h IntHeap // 最小堆用于维护当前k个节点
   heap.Init(&h) // 用于节点间的比较

   for _, list := range lists {
      // 数组中非空的链表加入到最小堆
      if list != nil {
         heap.Push(&h, list)
      }
   }
   // 定义dummy节点用于统一处理
   dummy := &ListNode{}
   p := dummy // p初始指向dummy节点

   // 当最小堆不为空时，不断执行以下操作
   for h.Len() > 0 { // 取出堆顶元素，即取出最小值节点
      min := heap.Pop(&h).(*ListNode)
      p.Next = min // 游标p指向最小值节点
      p = p.Next   // p向后移动一个位置
      // 这样就确定一个节点在合并链表中的位置
      if min.Next != nil { // 如果最小值节点后面的节点非空
         heap.Push(&h, min.Next) // 则把最小值节点后面的节点加入到最小堆中
      }
   }
   return dummy.Next // 最后只要返回dummy.Next即可
}

type IntHeap []*ListNode

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *IntHeap) Pop() interface{} {
   old := *h
   n := len(old)
   x := old[n-1]
   *h = old[0 : n-1]
   return x
}