21. 合并两个有序链表

const 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
    }
    prev.next = (l1 === null ? l2 : l1);
    return prehead.next
}

const mergeTwoLists = function(l1,l2){
  if(l1===null) return l2
  else if(l2===null) return l1
  else if(l1.val<l2.val){
    l1.next = mergeTwoLists(l1.next,l2)
    return l1
  }else{
    l2.next = mergeTwoLists(l1,l2.next)
    return l2
  }
}

总结：

• 使用空头指针的技巧
• <=``<都可以

23. 合并K个升序链表

var mergeKLists = function (lists) {
   return merge(lists, 0, lists.length - 1)
};

function merge(lists, l, r) {
    if (l === r) return lists[l]    // 一直递归到一个链表,返回该链表
    if (l > r) return null
    let mid = Math.floor((l + r) / 2)
    return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}

function mergeTwoLists(l1, l2) {...略}