跳至主要內容

148. 排序链表


148. 排序链表

🟠   🔖  链表 双指针 分治 排序 归并排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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. 首先,对链表进行分治,将链表一分为二。可以通过快慢指针找到链表的中点,然后分别对左右两部分进行排序。
  2. 对左右两个已排序的链表进行合并。合并两个有序链表的过程可以参考合并两个有序数组的算法。
  3. 递归地对左右两部分链表进行排序和合并,直到每个部分的长度为 1
  4. 最终得到一个完全有序的链表。

复杂度分析

  • 时间复杂度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合并两个有序链表[✓]递归 链表🟢🀄️open in new window 🔗open in new window
75颜色分类[✓]数组 双指针 排序🟠🀄️open in new window 🔗open in new window
147对链表进行插入排序[✓]链表 排序🟠🀄️open in new window 🔗open in new window
2046给按照绝对值排序的链表排序 🔒链表 双指针 排序🟠🀄️open in new window 🔗open in new window