合并K个排序链表

[louzhedong]

习题

出处：LeetCode 算法第23题

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

思路

通过数组构建，将链表中所有的元素存放到一个数组中，对数组进行排序，然后将数组构建成链表形式输出

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  var array = [];
  for (var i = 0, length = lists.lnegth; i < length; i++) {
    var temp = lists[i];
    while (temp != null) {
      array.push(temp.val);
      temp = temp.next;
    }
  }

  // array 包含了所有的元素
  array.sort(function (a, b) { return a - b });
  var result = new ListNode(0);
  var head = result;
  for (var i = 0, length = array.length; i < length; i++) {
    var newNode = new ListNode(array[i]);
    result.next = newNode;
    result = result.next;
  }

  return head.next;
};