Merge k sort linked lists

Merge k sort linked lists and return the merged sort linked lists. Please analyze and describe the complexity of the algorithm.

Examples:

Input:
 [
 1->4->5,
 1->3->4,
 2->6
 ]
 Output: 1->1->2->3->4->4->5->6

1. Violent cracking method

This solution is too violent, please use it carefully.

The principle is to disassemble, sort, and reassemble all nodes into a list. The reason is easy to understand.

The time complexity is O(nlogn)

2. Enumeration method

The main idea of this solution is to traverse the header values of all lists and push the smallest one into the current result queue.

The specific solution is

var isOver = function (lists) {
 let r = true
 lists.map(val => {
 if (val) {
 r = false
 return r
 }
 })
 
 return r
 }
 
 var minNode = function (lists) {
 let val = null
 let j
 for (var i = 0;   i < lists.length;  i++) {
 if (lists[i]) {
 if (val === null) {
 val = lists[i].val
 }
 // console.log(lists[i].val, val)
 if (lists[i].val <= val) {
 val = lists[i].val
 j = i
 }
 }
 }
 console.log(j)
 let m = new ListNode(lists[j].val)
 lists[j] = lists[j].next
 
 return m
 }
 
 var mergeKLists = function(lists) {
 if (lists.length === 0) return ''
 let result = null
 while (!  isOver(lists)) {
 if (!  result) {
 result = minNode(lists)
 } else {
 let z = result
 while (z.next) {
 z = z.next
 }
 z.next = minNode(lists)
 }
 }
 
 return result
 
 };

In the most extreme case, we need to traverse k linked lists every time we get elements, then the complexity is o (kn), and the higher the complexity of k value is. Not necessarily faster than the method

3. Partition Law

We only need to merge the adjacent lists, so we only need to do logN operations to merge the lists into an ordered list.

The recursion depth is logk in total, the recursion operation times of each layer are n times, and n is the number of all elements. So the total complexity is
O(nlogk)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
 /**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
 var mergeKLists = function(lists) {
 if(lists.length == 0) return null;
 var k = lists.length;
 while(k > 1){
 for (let i = 0;   i < ~~(k / 2);  i++) {
 lists[i] = mergeTwoLists(lists[i], lists[i + ~~((k + 1) / 2)]);
 }
 k = ~~((k + 1) / 2);
 }
 return lists[0];
 };
 var mergeTwoLists = function (l1, l2) {
 if (l1 == null) return l2
 if (l2 == null) return l1
 if (l1.val <= l2.val) {
 l1.next = mergeTwoLists(l1.next, l2)
 return l1
 } else {
 l2.next = mergeTwoLists(l1, l2.next)
 return l2
 }
 }

Submit