148. 排序链表
148. 排序链表
🟠 🔖 链表
双指针
分治
排序
归并排序
🔗 力扣
LeetCode
题目
Given the head
of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 10^4]
. -10^5 <= Node.val <= 10^5
Follow up: Can you sort the linked list in O(n logn)
time and O(1)
memory (i.e. constant space)?
题目大意
给你链表的头结点 head
,请将其按 升序 排列并返回 排序后的链表 。
进阶:你可以在 O(n log n)
时间复杂度和常数级空间复杂度下,对链表进行排序吗?
解题思路
使用归并排序(Merge Sort)对链表进行排序,归并排序的核心思想是分治和合并。
- 首先,对链表进行分治,将链表一分为二。可以通过快慢指针找到链表的中点,然后分别对左右两部分进行排序。
- 对左右两个已排序的链表进行合并。合并两个有序链表的过程可以参考合并两个有序数组的算法。
- 递归地对左右两部分链表进行排序和合并,直到每个部分的长度为
1
。 - 最终得到一个完全有序的链表。
复杂度分析
- 时间复杂度:
O(n log n)
,其中n
是链表的长度。通过归并排序,可以在链表排序中达到O(n log n)
的时间复杂度,且不需要额外的空间。 - 空间复杂度:
O(1)
,使用了常数级别的额外空间。
代码
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function (head) {
if (!head || !head.next) return head;
// 找到链表中点
const mid = findMid(head);
const left = head;
const right = mid.next;
mid.next = null; // 断开链表
// 递归对左右两部分进行排序
const sortLeft = sortList(left);
const sortRight = sortList(right);
// 合并两个有序链表
return merge(sortLeft, sortRight);
};
// 找到链表的中点(快慢指针)
var findMid = function (head) {
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};
// 合并两个有序链表
var merge = function (a, b) {
let res = new ListNode(0);
let cur = res;
while (a && b) {
if (a.val < b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
// 处理剩余的节点
if (a) {
cur.next = a;
}
if (b) {
cur.next = b;
}
return res.next;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
21 | 合并两个有序链表 | [✓] | 递归 链表 | 🟢 | 🀄️ 🔗 |
75 | 颜色分类 | [✓] | 数组 双指针 排序 | 🟠 | 🀄️ 🔗 |
147 | 对链表进行插入排序 | [✓] | 链表 排序 | 🟠 | 🀄️ 🔗 |
2046 | 给按照绝对值排序的链表排序 🔒 | 链表 双指针 排序 | 🟠 | 🀄️ 🔗 |