Open xszi opened 3 years ago
let sortList = function(head) {
return mergeSortRec(head)
}
// 归并排序
// 若分裂后的两个链表长度不为 1,则继续分裂
// 直到分裂后的链表长度都为 1,
// 然后合并小链表
let mergeSortRec = function (head) {
if(!head || !head.next) {
return head
}
// 获取中间节点
let middle = middleNode(head)
// 分裂成两个链表
let temp = middle.next
middle.next = null
let left = head, right = temp
// 继续分裂(递归分裂)
left = mergeSortRec(left)
right = mergeSortRec(right)
// 合并两个有序链表
return mergeTwoLists(left, right)
}
// 获取中间节点
// - 如果链表长度为奇数,则返回中间节点
// - 如果链表长度为偶数,则有两个中间节点,这里返回第一个
let middleNode = function(head) {
let fast = head, slow = head
while(fast && fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}
// 合并两个有序链表
let mergeTwoLists = function(l1, l2) {
let preHead = new ListNode(-1);
let cur = preHead;
while(l1 && l2){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 || l2;
return preHead.next;
}
引入递归算法的复杂度分析:
复杂度分析
时间复杂度:递归的总次数为 T(logn) ,每次递归的数量为 T(n) ,时间复杂度为 O(nlogn) 空间复杂度:递归的深度为 T(logn) ,每次递归创建变量的个数为 T(c) (c为常数),空间复杂度为 O(logn)
var sortList = function (head) {
const sentinelNode = new ListNode(0); // 哨兵结点
sentinelNode.next = head;
let len = 0, p = head;
while (p) {
p = p.next;
len++;
}
for (let i = 1; i < len; i <<= 1) {
let cur = sentinelNode.next, // 当前结点
pre = sentinelNode; // 当前结点的前一个
while (cur) {
const left = cur;
const right = cut(left, i); // 切割得到第二链表
cur = cut(right, i); // 切割得到后面需要遍历的链表
pre.next = merge(left, right); // 将得到的两个链表归并
while (pre.next) {
pre = pre.next;
}
}
}
return sentinelNode.next;
};
/* 切割并返回后面的链表 */
const cut = (head, n) => {
let p = head;
while (--n && p) {
p = p.next;
}
if (!p) return null;
const next = p.next;
p.next = null;
return next;
};
/* 将两个已经排序的链表归并 */
const merge = (l1, l2) => {
const sentinelNode = new ListNode(0);
let p = sentinelNode;
while (l1 && l2) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
p.next = l1 ? l1 : l2; // 将其中一个有剩余结点的链表加在之后
return sentinelNode.next;
};
复杂度分析
时间复杂度:时间复杂度为 O(n) 空间复杂度:空间复杂度为 O(1)
在
O(nlogn)
时间复杂度和常数级空间复杂度下,对链表进行排序。示例 1:
示例 2:
leetcode