排序链表
解题思路：
-
找到链表的中点，以中点为分界，将链表拆分成两个子链表；（876. 链表的中间结点）
-
对两个子链表分别排序；
-
将两个排序后的子链表合并，得到完整的排序后的链表；（21. 合并两个有序链表）
图解：
复杂度：
-
时间复杂度：O(nlogn)，其中 n 是链表的长度；
-
空间复杂度：O(logn)，其中 n 是链表的长度，空间复杂度主要取决于递归调用的栈空间；
代码实现：
function sortList(head: ListNode | null): ListNode | null {
// 终止条件
if (head == null || head.next == null) {
return head;
}
// 获取链表中间节点
let midNode = getMiddleNode(head);
let rightHead = midNode.next;
// 断开链表
midNode.next = null;
let left = sortList(head);
let right = sortList(rightHead);
// 合并有序链表
return mergeTwoLists(left, right);
}
// 利用快慢指针找到中间节点
var getMiddleNode = function (head: ListNode | null): ListNode | null {
if (head == null || head.next == null) {
return head;
}
let slow = head;
let fast = head.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
// 合并两个有序链表
var mergeTwoLists = function (l1: ListNode | null, l2: ListNode | null): ListNode | null {
let dmy = { next: null };
let curr = dmy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return dmy.next;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
1797.设计一个验证系统（滴滴）
上一篇
评论
