合并K个升序链表

// 参数
/**
 * 
 * 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}
 */

// 这个方式是，每次都找最小的节点，然后插入到新的链表中
// 将每个链的第一个节点进行排序，使用了的链，移除第一个节点后，重新排序进去。
var mergeKLists = function(lists) {
  lists = lists.filter(list => !!list)
  if (lists.length === 0) {
    return null
  }
  const fullList = {
    list: null,
    next: {list: lists.pop(), next: null}
  }
  lists.forEach(list => {
    insertListNode(fullList, list)
  })
  let result = {
    next: null
  }, curNode = result
  while(true) {
    if (fullList.next) {
      const listNode = fullList.next;
      fullList.next = listNode.next;
      const list = listNode.list;
      curNode.next = list;
      curNode = curNode.next;
      insertListNode(fullList, list.next);
    } else {
      break
    }
  }
  return result.next
};
 
function insertListNode(fullList, list) {
  if (!!list) {
    let preNode = fullList
    while(true) {
      const nextNode = preNode.next;
      if (!nextNode) {
        preNode.next = {
          list: list,
          next: null
        }
        break;
      } else if (list.val < nextNode.list.val) {
        preNode.next = {
          list: list,
          next: nextNode
        }
        break;
      }
      preNode = nextNode;
    }
  }
}

// 这个方式就是最简单粗暴的，将每个链表的节点值和节点进行关联，然后对节点值进行排序，然后进行合并
var mergeKLists = function(lists) {
  var obj = {};
  lists.forEach(list => {
    while(list) {
      const next = list.next
      if (obj[list.val]) {
        list.next = obj[list.val][0]
        obj[list.val].unshift(list)
      } else {
        obj[list.val] = [list]
        list.next = null
      }
      list = next
    }
  })
  const result = {
    next: null
  }
  let curNode = result
  Object.keys(obj).map(Number).sort(((a, b) => a-b)).forEach(key => {
    curNode.next = obj[key][0]
    curNode = obj[key].pop()
  })
  return result.next
}