合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例 :
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
实现思路很多,比如:
1.双指针+合并2.递归 + 分治3.优先级队列4.转换为数组求解
我们以递归+分支思路为例
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
let n = lists.length;
if (n == 0) return null;
let mergeTwoLists = (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;
}
}
let merge = (left, right) => {
if (left == right) return lists[left];
let mid = (left + right) >> 1;
let l1 = merge(left, mid);
let l2 = merge(mid + 1, right);
return mergeTwoLists(l1, l2);
}
return merge(0, n - 1);
};
Link点击事件handleClick部分源码
if (_this.props.onClick) _this.props.onClick(event);
if (!event.defaultPrevented && // onClick prevented default
event.button === 0 && // ignore everything but left clicks
!_this.props.target && // let browser handle "target=_blank" etc.
!isModifiedEvent(event) // ignore clicks with modifier keys
) {
event.preventDefault();
var history = _this.context.router.history;
var _this$props = _this.props,
replace = _this$props.replace,
to = _this$props.to;
if (replace) {
history.replace(to);
} else {
history.push(to);
}
}
Link做了3件事情:
1.有onclick那就执行onclick2.click的时候阻止a标签默认事件(这样子点击[123]()
就不会跳转和刷新页面)3.再取得跳转href(即是to),用history(前端路由两种方式之一,history & hash)跳转,此时只是链接变了,并没有刷新页面
[1]
23. 合并K个排序链表: https://leetcode-cn.com/problems/merge-k-sorted-lists/
本文分享自 JavaScript全栈 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!