Leetcode 23 questions

Topic:

Merge k sorted lists and return the merged sorted lists. Analyze and describe the complexity of the algorithm.

Example:
Input: [1 - > 4 - > 5, 1 - > 3 - > 4, 2 - > 6] output: 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

Idea 1:

The first time I got the problem, I thought of merging two sorted lists. The easy solution is to do an honest merge of two lists.

/** * @param {ListNode[]} lists * @return {ListNode} */
var mergeKLists = function(lists) {
    while(lists.length>1){
        lists.push(merge(lists.pop(),lists.pop()));
    }
    return lists.pop() || null;
};

// Merge two lists
function merge(l1,l2){
    if(l1==null) return l2;
    if(l2==null) return l1;
    let p = l1, q = l2;
    let res = new ListNode();
    let i = res;
    while(p! =null&& q! = =null) {if(p.val<q.val){
            i.next = p;
            p = p.next;
        }else{
            i.next = q;
            q = q.next;
        }
        i = i.next;
    } 
    i.next = p==null? q:p;return res.next;
}
Copy the code

Idea 2:

Just turn the list into an array, sort the array, and then go back to the list.

Do not recommend the use of this method does not conform to the topic of people’s thinking, belonging to the opportunistic type, but as a way to expand the reference

var mergeKLists = function(lists) {
    // First convert to an array
    let arr = [];
    for(let l of lists){
        while(l){ arr.push(l.val); l=l.next; }}// Array sort
    arr.sort((a,b) = >a-b);
    // Convert to a linked list
    let res = new ListNode();
    let p = res;
    for(let i of arr){
        p.next = new ListNode(i);
        p=p.next;
    }
    return res.next
};
Copy the code

Idea 3:

Every time two lists are taken out and combined, there will be many repeated comparisons. So I came up with a way to sort each list by putting the smallest value in an array. Then place the minimum value in the current array in the return list, move the current minimum list back, and continue to insert into the array in order.

var mergeKLists = function(lists) {
    // Insert the smallest of the K lists into the array and sort by value
    let arr = [],res=new ListNode(),p=res;
    for(let l of lists){
        orderInsert(arr,l);
    }
    // Remove the minimum value each time and place it in the return list, then move the list back and place it in the array
    while(arr.length>1) {let [i,temp] = arr.pop();
        p.next = temp;
        temp = temp.next;
        p = p.next;
        orderInsert(arr,temp);
    }
    // Put the last group in the last call
    p.next = arr[0]? arr[0] [1] :null;
    return res.next;
};

// Insert in sequence
function orderInsert(arr,l){
    if(l==null) return;
    let val = l.val,index = 0, temp = [val,l];
    for(let i=0; i<arr.length; i++){if(arr[i][0]<=val){
            arr.splice(i,0,temp)
            return;
        }
    }
    arr.push(temp);
}
Copy the code

Conclusion:

This problem is not at all hard, but none of the solutions I have come up with are low in time complexity. That means it’s not hard to solve, but it takes a little bit of thinking to get to the optimal solution.