LeetCode-23. Merge K Sorted Lists

发表于 分类于

问题描述

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

1
2
Input: lists = []
Output: []

Example 3:

1
2
Input: lists = [[]]
Output: []

解答

使用归并排序的思想

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 * @Description: 23. Merge k Sorted Lists
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
const mergeKLists = function (lists) {
  if (!lists.length) {
      return null
  }
  return divideMerge(lists, 0, lists.length - 1)
}

function divideMerge (lists, left, right) {
  if (left === right) {
    return lists[left]
  }
  let mid = Math.floor((left + right) / 2)
  return merge(divideMerge(lists, left, mid), divideMerge(lists, mid + 1, right))
}

function merge (listLeft, listRight) {
  if (listLeft === null || listRight === null) {
    return listLeft || listRight
  }
  const newHead = new ListNode()
  let pre = newHead
  while (listLeft && listRight) {
    if (listLeft.val < listRight.val) {
      pre.next = listLeft
      listLeft = listLeft.next
    } else {
      pre.next = listRight
      listRight = listRight.next
    }
    pre = pre.next
  }
  pre.next = (listLeft === null) ? listRight : listLeft
  return newHead.next
}