/**
* 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) {

  // 结合先前做的合并两个有序列表,这里可以很自然的想到,暴力一点,笨一点
  // 每次只处理两个链表,慢慢来

  var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);

     let prev = prehead;
     while (l1 != null && l2 != null) {
         if (l1.val <= l2.val) {
             prev.next = l1;
             l1 = l1.next;
         } else {
             prev.next = l2;
             l2 = l2.next;
         }
         prev = prev.next;
     }

     // 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
     prev.next = l1 === null ? l2 : l1;

     return prehead.next;
  };

  let newNode = new ListNode()
    // new List(Number.NEGATIVE_INFINITY),改为这样就ok了
  let tempNode = newNode
  while (lists.length) {
  let arrNode = lists.shift()
  tempNode = mergeTwoLists(tempNode, arrNode)
  }
  return newNode.next
};
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

这个版本代码的问题在于,一开始初始值是0,那就导致数组中的第一项有可能在合并后被更小的项替换,比如-1。这也是过不了[[2], [], [-1]]这个case的原因,但是尝试往new

一笔写于: 4/23/2022, 7:06:34 PM
扫码添加我的微信
个人
个人号
公众号
公众号