21. 合并两个有序链表

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let dummy = new ListNode();
    let cur = dummy;

    while(list1&&list2){
        if(list1.val<list2.val){
            cur.next = list1;
            list1 = list1.next;
        }else{
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }

    if(list1||list2){
        cur.next = list1 || list2;
    }
    return dummy.next;
};

23. 合并 K 个升序链表

基于合并两个升序链表的分治解法；

const mergeTwoLists=(lists1:any, lists2:any):any=>{
    if(!lists1||!lists2) return lists1 ?? lists2 ?? null
    
    let dummy = new ListNode(0);
    let cur = dummy;
    
    while(lists1&&lists2){

        if(lists1.val<lists2.val){
            cur.next = lists1;
            lists1 = lists1.next;
        }else{
            cur.next = lists2;
            lists2 = lists2.next;
        }
        cur = cur.next;
    }

    cur.next = lists1 || lists2;

    return dummy.next;
}

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    const len = lists.length
    const dfs = (i:number, j:number) => {
        const m = j - i;
        if(m===0) return null;
        if(m===1) return lists[i]
        let left = dfs(i, i+Math.floor(m/2))
        let right = dfs(i+Math.floor(m/2),j)
        return mergeTwoLists(left, right);
    }

    return dfs(0, len)
};