52.算法->合并k个升序的链表

day4：算法->合并k个升序链表

思路：乍一看又是数组又是链表的怎么肥事。
先来理解一下题目：给定一个数组，数组里面存的项是多个链表，此时我们不由地想起来之前做过合并两个升序链表的问题，这不就来思路了。

• 暴力求解法：先将链表中所有项都存入数组，利用数组的sort方法进行排序，再将链表返回
• 分而治之：（听起来很高大上，不懂是什么意思）其实就是将多了链表进行分组，然后进行两两合并
• 优先级队列：没有看懂錒🤣

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 * 两两合并
 *
 */
var mergeKLists = function (lists) {
  //需要判断为空的情况
  if (null == lists || lists.length == 0) {
    return null;
  }
  //两两进行合并，创建一个空的链表或者将第一个作为链表头都可以
  let newList = lists[0];
  for (let i = 1; i < lists.length; i++) {
    let listi = lists[i];
//每次返回的结果就是两个链表合并后的结果，依次进行合并即可
    newList = mergeTwoLists(newList, listi);
    console.log("newList", newList);
  }
  return newList;
};

var mergeTwoLists = function (l1, l2) {
  console.log(l1, l2);
  let newlist = new ListNode(0);
  let head = newlist;
  while (l1 && l2) {
    if (l1.val < l2.val) {
      head.next = l1;
      l1 = l1.next;
    } else {
      head.next = l2;
      l2 = l2.next;
    }
    head = head.next;
  }
  if (l1) {
    head.next = l1;
  }
  if (l2) {
    head.next = l2;
  }
  return newlist.next;
};


//分而治之
function mergeKLists1(lists) {
  return merge(lists, 0, lists.length);
}
function merge(lists, l, r) {
  if (l == r) {
    return lists[l];
  }
  if (l > r) {
    return null;
  }
//一个很巧妙的地方，利用位移运算，可以直接求出平均值，相当于Math.ceil()
  let mid = (l + r) >> 1;
  return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
//第二种方法，当 l!=r的时候，继续进行分组，直到 l=r开始进行参与合并运算
// mid = 1 ,l=0,r=2,mergeTwoLists(merge(lists,0,1),merge(lists,2,2))[-2, -1, 0, 2]
// mid = 0 ,l=0,r=1,mergeTwoLists(merge(lists,0,0),merge(lists,1,1))[-1, 1][-3, 1, 4]

不懂什么是位运算符的看这里->位运算符
想证明一下【利用位移运算，可以直接求出平均值】的看这个【十进制转二进制】、【二进制转十进制】