LeetCode-23.合并k个有序链表

发表于 分类于

题目描述

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

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

示例：

1
2
3
4
5
6
7
8
9
10
输入：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
1
2
输入：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

题解

归并思想

如果是两个有序链表合并，我们可能会利用归并排序合并阶段的思想：准备双指针分别放在两个链表头，每次取出较小的一个元素加入新的大链表，将其指针后移，继续比较，这样我们出去的都是最小的元素，自然就完成了排序。

其实只要遍历链表数组，取出开头的两个链表，按照上述思路合并，然后新链表再与后一个继续合并，如此循环，直到全部合并完成。但是，这样太浪费时间了。

既然都是归并排序的思想了，那我们可不可以直接归并的分治来做，而不是顺序遍历合并链表呢？答案是可以的！

归并排序是什么？简单来说就是将一个数组每次划分成等长的两部分，对两部分进行排序即是子问题。对子问题继续划分，直到子问题只有1个元素。还原的时候呢，将每个子问题和它相邻的另一个子问题利用上述双指针的方式，1个与1个合并成2个，2个与2个合并成4个，因为这每个单独的子问题合并好的都是有序的，直到合并成原本长度的数组。

  1. 对于这k个链表，就相当于上述合并阶段的k个子问题，需要两个合并，不断往上，最终合并成完整的一个链表。
  2. 从链表数组的首和尾开始，每次划分从中间开始划分，划分成两半。
  3. 将这两半子问题合并好了就成了两个有序链表，最后将两个有序链表合并就成了，依据子问题递归处理。
  • 终止条件： 划分的时候直到左右区间相等或左边大于右边。
  • 返回值： 每级返回已经合并好的子问题链表。
  • 本级任务： 对半划分，将划分后的子问题合并成新的链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
  return devideList(lists, 0, lists.count - 1)
}

func devideList(_ lists: [ListNode?], _ begin: Int, _ end: Int) -> ListNode? {
  if begin > end {
    return nil
  }
  if begin == end {
    return lists[begin]
  }
  let middle = (begin + end) / 2;
  let left = devideList(lists, begin, middle)
  let right = devideList(lists, middle + 1, end)
  return mergeTwoLists(left, right)
}
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
  if list1 == nil {
    return list2
  }
  if list2 == nil {
    return list1
  }
  let value1 = list1!.val
  let value2 = list2!.val
  if value1 <= value2 {
    list1?.next = mergeTwoLists(list1?.next, list2)
    return list1
  } else {
    list2?.next = mergeTwoLists(list1, list2?.next)
    return list2
  }
}