K-sorted linked lists algo

Question

I was doing k sorted linked list also at leetcode.

Question: Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Question Link: https://leetcode.com/problems/merge-k-sorted-lists/submissions/

Example:

Input:

[
  1->4->5,
  1->3->4,
  2->6
]

Output: 1->1->2->3->4->4->5->6

Where Input of this

[[1,4,5],[1,3,4],[2,6]]

would actually look something like this (when passed)

[ ListNode { val: 1, next: ListNode { val: 4, next: [ListNode] } },
  ListNode { val: 1, next: ListNode { val: 3, next: [ListNode] } },
  ListNode { val: 2, next: ListNode { val: 6, next: null } } ]

So anyway, I wrote this code

 // converts input array to object
const arrayToObject = (lists) => {
    if (lists.length === 0) return lists 
    else {
        let linkedListMergedArray = []
        for (let i=0; i<lists.length; i++) {
            const itterationItem = lists[i]
            const reduceToArray = recursivelyCreateArray(itterationItem)
            if (reduceToArray) linkedListMergedArray = [...linkedListMergedArray, ...reduceToArray ]
        }
     return linkedListMergedArray
    }
}
// breaks down the object to linkedList 
const recursivelyCreateArray = (listObject) => {
    if (!listObject) return null
    if (Array.isArray(listObject)) return arrayToObject(listObject)
    if (!listObject.next) return [listObject.val]
    else return [listObject.val, ...recursivelyCreateArray(listObject.next)]
}

// creates an object which looks like { val: value, next { val: value
const convertMergedArrayToOutputLinkedList = (mergedArray, i=0) => {
    if (!mergedArray[i]) return null
    else return {
        val: mergedArray[i],
        next: convertMergedArrayToLinkedList(mergedArray, i+1)
    }
}

//starting point of code
var mergeKLists = function(lists) {
 const linkedListToArray = arrayToObject(lists)
 if (linkedListToArray.length > 0) {
     const sortArray = linkedListToArray.sort((a,b) => a-b)
     return convertMergedArrayToOutputLinkedList(sortArray)
 } else return null
};

But this is failing for following input [[0,2,5]]

while, I am still debugging it, I have a feeling that this isn't optimal algo so can someone please help me in writing an optimised code and also, In figuring out what I could be doing wrong?

@NinaScholz Which line are you referring to? unable to get you here. — Alwaysblue
– Alwaysblue, Commented Nov 4, 2019 at 22:09
it makes sense in having this data, but not in the result, imho. — Nina Scholz
– Nina Scholz, Commented Nov 4, 2019 at 22:17
@NinaScholz The question asks the coder to merge the given lists. It doesn't ask to remove duplicates. — Code-Apprentice
– Code-Apprentice, Commented Nov 4, 2019 at 23:32

grodzi · Accepted Answer · 2019-11-04 23:08:01Z

easy way

An obvious solution is to simply merge all your list then sort the result. O(nlogn). It is worth noting because in reality, this is almost a oneliner without much trouble.

    function ez(heads){
        function toArr(l){
            v=[]
            while(l){v.push(l.val); l=l.next}
            return v;
        }
        return heads.map(toArr).flatMap(l=>l).sort((a,b)=>a-b)
    }

faster way

If you want moar perf, (O(n))

Imagine you have three cursors (one for each list).

At a time t, you select the smallest element pointed by your cursors. And you move that cursor to the next element of its list. goto.

You obviously initialize your cursors at the head of each list.

    function linear(heads){
        function min(heads){//inspect all cursors and get the min
            let idx = -1;
            let val = 9000;
            for(let i = 0; i<heads.length; ++i){
                if(heads[i] && heads[i].val<val){
                    val = heads[i].val;
                    idx = i;
                }
            }
            return {idx, val}
        }
        let stack = [];
        while(true){
            let {idx, val}=min(heads);
            if(idx == -1){
                break
            }
            stack.push(val);
            heads[idx] = heads[idx].next; //move the cursor.
        }
        return stack;
    }

verification

Finally it is here not much trouble to check the theoritical faster way is indeed faster:

    function ez(heads){
        function toArr(l){
            v=[]
            while(l){v.push(l.val); l=l.next}
            return v;
        }
        return heads.map(toArr).flatMap(l=>l).sort((a,b)=>a-b)
    }
    function linear(heads){
        function min(heads){
            let idx = -1;
            let val = 1000;
            for(let i = 0; i<heads.length; ++i){
                if(heads[i] && heads[i].val<val){
                    val = heads[i].val;
                    idx = i;
                }
            }
            return {idx, val}
        }
        let stack = [];
        while(true){
            let {idx, val}=min(heads);
            if(idx == -1){
                break
            }
            stack.push(val);
            heads[idx] = heads[idx].next
        }
        return stack;
    }
    
    let arr = [
    Array(700).fill(0).map(x=>Math.random()).sort((a,b)=>a-b),
    Array(700).fill(0).map(x=>Math.random()).sort((a,b)=>a-b),
    Array(700).fill(0).map(x=>Math.random()).sort((a,b)=>a-b)
];
//just create the linked lists
let heads = arr.map(x=>x.reduce((acc,val)=>{
    acc.cur.next = {val, next:null}
    if(acc.head == null){
        acc.head = acc.cur.next
    }
    acc.cur = acc.cur.next;
    return acc;
},{head:null, cur:{}})).map(x=>x.head)
console.time('ez')
ez(heads)
console.timeEnd('ez'); //4ms for me
console.time('linear')
linear(heads)
console.timeEnd('linear'); //2ms for me

I advise you to test for different sizes, you will notice that the ez way is faster until some length is reached.

note that it is voluntary not to give back a linked list. (I believe it is not of interest and even if it was, op should workout a bit!)
Just by looking at your code, it makes me feel I am such a bad coder, You reduced my infinite long code to just 6-7 line of code. wow.

Collectives™ on Stack Overflow

K-sorted linked lists algo

1 Answer 1

easy way

faster way

verification

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

easy way

faster way

verification

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related