题目

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：

[

1->4->5,

1->3->4,

2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

示例 2：输入：lists = [] 输出：[]

示例 3：输入：lists = [[]] 输出：[]

提示：k == lists.length

0 <= k <= 10^4

0 <= lists[i].length <= 500

-10^4 <= lists[i][j] <= 10^4

lists[i] 按 升序 排列

lists[i].length 的总和不超过 10^4

注意：本题与主站 23 题相同：

解题思路分析

1、顺序合并；时间复杂度O(n^2)，空间复杂度O(1)

func mergeKLists(lists []*ListNode) *ListNode {
   if len(lists) == 0 {
      return nil
   }
   temp := &ListNode{}
   for i := 0; i < len(lists); i++ {
      temp.Next = mergeTwoLists(temp.Next, lists[i])
   }
   return temp.Next
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
   res := &ListNode{}
   temp := res
   for l1 != nil && l2 != nil {
      if l1.Val < l2.Val {
         temp.Next = l1
         l1 = l1.Next
      } else {
         temp.Next = l2
         l2 = l2.Next
      }
      temp = temp.Next
   }
   if l1 != nil {
      temp.Next = l1
   } else {
      temp.Next = l2
   }
   return res.Next
}

2、归并合并；时间复杂度O(nlog(n))，空间复杂度O(log(n))

func mergeKLists(lists []*ListNode) *ListNode {
   if len(lists) == 0 {
      return nil
   }
   if len(lists) == 1 {
      return lists[0]
   }
   first := mergeKLists(lists[:len(lists)/2])
   second := mergeKLists(lists[len(lists)/2:])
   return mergeTwoLists(first, second)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
   res := &ListNode{}
   temp := res
   for l1 != nil && l2 != nil {
      if l1.Val < l2.Val {
         temp.Next = l1
         l1 = l1.Next
      } else {
         temp.Next = l2
         l2 = l2.Next
      }
      temp = temp.Next
   }
   if l1 != nil {
      temp.Next = l1
   } else {
      temp.Next = l2
   }
   return res.Next
}

3、堆排序；时间复杂度O(nlog(n))，空间复杂度O(log(n))

func mergeKLists(lists []*ListNode) *ListNode {
   if len(lists) == 0 {
      return nil
   }
   var h IntHeap
   heap.Init(&h)
   for i := 0; i < len(lists); i++ {
      if lists[i] != nil {
         heap.Push(&h, lists[i])
      }
   }
   res := &ListNode{}
   temp := res
   for h.Len() > 0 {
      minItem := heap.Pop(&h).(*ListNode)
      temp.Next = minItem
      temp = temp.Next
      if minItem.Next != nil {
         heap.Push(&h, minItem.Next)
      }
   }
   return res.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
}

4、自定义排序；时间复杂度O(nlog(n))，空间复杂度O(n)

func mergeKLists(lists []*ListNode) *ListNode {
   if len(lists) == 0 {
      return nil
   }
   arr := make([]*ListNode, 0)
   for i := 0; i < len(lists); i++ {
      temp := lists[i]
      for temp != nil {
         arr = append(arr, temp)
         temp = temp.Next
      }
   }
   if len(arr) == 0 {
      return nil
   }
   sort.Slice(arr, func(i, j int) bool {
      return arr[i].Val < arr[j].Val
   })
   for i := 0; i < len(arr)-1; i++ {
      arr[i].Next = arr[i+1]
   }
   arr[len(arr)-1].Next = nil
   return arr[0]
}

总结

Hard题目，题目同leetcode 23.合并K个排序链表