【算法解析LeetCode by Javascript】23. 合并K个排序链表

合并K个排序链表合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->61.暴力破解法此解法过于暴力，请谨慎使用原理就是把所有的节点拆解，排序，再从新组合成一个列表，道理容易理解时间复杂度为 O(nlogn)2.枚举法此解法的主要思路为遍历所有列表的头部值，把最小的一个推入到当前结果队列里具体解法为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 };最极端的情况下我们每次获取元素都需要遍历k个链表，那么复杂度就是O(kn),k值复杂度越高。不一定比方法-更快3.分治法我们只需要把相邻列表进行合并，这样的话我们只需要进行logN次操作就可以把列表归并成一个有序列表递归深度一共是logk，每一层的递归操作次数都是n次，n是所有元素的个数。那么总的复杂度就是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 }}提交