题目描述：

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
**示例:

  1. 输入:
  2. [
  3.   1->4->5,
  4.   1->3->4,
  5.   2->6
  6. ]
  7. 输出: 1->1->2->3->4->4->5->6

算法实现：

JavaScript

递归暴力法

  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.     switch(lists.length) {
  14.         case 0:
  15.             return null
  16.         case 1:
  17.             return lists[0]
  18.         case 2:
  19.             return merge2Lists(lists[0], lists[1])
  20.         default: 
  21.             let mid = Math.round(lists.length / 2)
  22.             return merge2Lists(mergeKLists(lists.slice(0, mid)), 
  23.                             mergeKLists(lists.slice(mid, lists.length)))
  24.     }
  25. };
  26. function merge2Lists (l1, l2) {
  27.     var listToArray = (list) => {
  28.         if(list == null) {
  29.             return []
  30.         } else if(list.next) {
  31.             return [list.val, ...listToArray(list.next)]
  32.         } else {
  33.             return [list.val]
  34.         }
  35.     }
  36.     var arrSort = (arr) => {
  37.         arr.sort((a, b) => a - b) 
  38.         return arr
  39.     }
  40.     var arrayToList = (arr) => {
  41.         if(arr.length > 0) {
  42.             let node = new ListNode(arr.shift())
  43.             node.next = arrayToList(arr)
  44.             return node
  45.           } else {
  46.             return null
  47.         }
  48.     }
  49.     return arrayToList(arrSort([...listToArray(l1),...listToArray(l2)]))
  50. }

递归法

  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.     switch(lists.length) {
  14.         case 0:
  15.             return null
  16.         case 1:
  17.             return lists[0]
  18.         case 2:
  19.             return merge2Lists(lists[0], lists[1])
  20.         default: 
  21.             let mid = Math.round(lists.length / 2)
  22.             return merge2Lists(mergeKLists(lists.slice(0, mid)), 
  23.                             mergeKLists(lists.slice(mid, lists.length)))
  24.     }
  25. };
  26. function merge2Lists (l1, l2) {
  27.    if(l1 === null){
  28.         return l2
  29.     }
  30.     if(l2 === null){
  31.         return l1
  32.     }
  33.     if(l1.val < l2.val){
  34.         l1.next = merge2Lists(l1.next, l2)
  35.         return l1
  36.     }else{
  37.         l2.next = merge2Lists(l1, l2.next)
  38.         return l2
  39.     }
  40. }

思考：

本题由上题改变而来，可以应用上题的暴力法或递归法解决。

总结：

在实现递归的过程中遇到了很多的困难，改bug改了四五个小时，最终也没有通过自己的想法实现，最后借鉴了别人的代码，勉强通过了。