[LeetCode][JavaScript]Merge k Sorted Lists

Merge k Sorted Lists

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

https://leetcode.com/submissions/detail/28015840/

直接使用了“Merge Two Sorted Lists”里写的方法。

http://www.cnblogs.com/Liok3187/p/4514347.html

两两比较就好了，每一轮比较都会减少一半lists的数量。

 1 /**
 2  * Definition for singly-linked list.
 3  * function ListNode(val) {
 4  *     this.val = val;
 5  *     this.next = null;
 6  * }
 7  */
 8 /**
 9  * @param {ListNode[]} lists
10  * @return {ListNode}
11  */
12 var mergeKLists = function(lists) {
13     function mergeTwoLists(l1, l2) {
14         var i = l1, j = l2;
15         var res = new ListNode(-1);
16         curr = res;
17         while(i && j && i.val !== undefined && j.val !== undefined){
18             if(i.val < j.val){
19                 curr.next = i;
20                 i = i.next;
21             }else{
22                 curr.next = j;
23                 j = j.next;
24             }
25             curr = curr.next;     
26         }
27         if(i && i.val !== undefined){
28             curr.next = i;
29         }
30         if(j && j.val !== undefined){
31             curr.next = j;
32         }
33         return res.next || [];
34     }
35     
36     var k;
37     while(lists.length >= 2){
38         var tmpList = [];
39         for(k = lists.length - 1; k >= 0; k-=2){
40             tmpList.push(mergeTwoLists(lists[k], lists[k - 1]));
41         }
42         if(k === 0){
43             tmpList.push(lists[0]);
44         }
45         lists = tmpList;
46     }
47     
48     return lists[0] || [];
49 };