1269.停在原地的方案数

链接：1269.停在原地的方案数
难度：Hard
标签：动态规划
简介：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

题解 1 - typescript

• 编辑时间：2021-05-13
• 执行用时：220ms
• 内存消耗：48.3MB
• 编程语言：typescript
• 解法介绍：归并思想排序。

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  lists = lists.filter(list => list !== null);
  const len = lists.length;
  if (len === 0) return null;
  const merge = (start: number, end: number): ListNode | null => {
    console.log(start, end);
    if (start > end) return null;
    if (start === end) return lists[start];
    const mid = (start + end) >> 1;
    const list1 = merge(start, mid);
    const list2 = merge(mid + 1, end);
    if (list1 === null) return list2;
    if (list2 === null) return list1;
    const first = new ListNode(0);
    let temp = first;
    let p1: ListNode | null = list1;
    let p2: ListNode | null = list2;
    while (p1 && p2) {
      if (p1.val <= p2.val) {
        temp.next = p1;
        temp = temp.next;
        p1 = p1.next;
      } else {
        temp.next = p2;
        temp = temp.next;
        p2 = p2.next;
      }
    }
    if (p1) temp.next = p1;
    if (p2) temp.next = p2;
    return first.next;
  };
  return merge(0, len - 1);
}

题解 2 - javascript

• 编辑时间：2020-04-26
• 执行用时：404ms
• 内存消耗：37.3MB
• 编程语言：javascript
• 解法介绍：循环数组进行添加，把数组两两添加，添加时判断数值小以及是否为 null。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (lists.length === 0) return null;
  if (lists.length === 1) return lists[0];
  let resNode;
  for (const node of lists) {
    if (node === null) continue;
    if (resNode === undefined) resNode = node;
    else resNode = add(resNode, node);
  }
  return resNode === undefined ? null : resNode;
};
function add(node1, node2) {
  let tempNode1 = node1;
  let tempNode2 = node2;
  let resNode;
  let tempNode3;
  while (tempNode1 !== null || tempNode2 !== null) {
    let minNode;
    if (tempNode1 === null) {
      minNode = tempNode2;
      tempNode2 = tempNode2.next;
    } else if (tempNode2 === null) {
      minNode = tempNode1;
      tempNode1 = tempNode1.next;
    } else if (tempNode1.val < tempNode2.val) {
      minNode = tempNode1;
      tempNode1 = tempNode1.next;
    } else {
      minNode = tempNode2;
      tempNode2 = tempNode2.next;
    }
    if (resNode === undefined) {
      tempNode3 = resNode = minNode;
    } else {
      tempNode3.next = minNode;
      tempNode3 = tempNode3.next;
    }
  }
  return resNode;
}