leetcode148-排序链表
leetcode 148
思路
- 遍历链表并收集节点：将链表中的每个节点断开其 next 指针后存入数组
- 对数组进行排序：使用 JavaScript 的内置 sort 方法对节点数组按值排序
- 重新连接排序后的节点：遍历排序后的数组，依次连接每个节点形成新链表
时间复杂度：O (n log n) 空间复杂度：O (n)
实现
var sortList = function (head) {if (!head) return head;let cur = head;const arr = [];while (cur) {const node = cur.next;cur.next = null;arr.push(cur);cur = node;}arr.sort((a, b) => a.val - b.val)let result = arr[0];cur = result;for (let i = 1; i < arr.length; i++) {cur.next = arr[i]cur = cur.next;}return result;
};
优化-归并排序
上面的解法简单直观，会更容易理解，但是空间复杂度是O(n)，利用归并排序可以将空间复杂度优化到O(1)
归并思路
归并排序的核心思想是分治法：
- 分割：将链表从中间分成两部分
- 使用快慢指针法找到链表中点
- 断开中点连接，形成两个独立子链表
- 递归排序：分别对左右子链表递归进行排序
- 递归处理每个子链表，直到链表为空或只剩一个节点（自然有序）
- 合并：将两个有序子链表合并为一个有序链表
- 使用虚拟头节点（dummy node）简化合并操作
- 比较两个子链表的节点值，按升序连接
关键步骤解析
- 快慢指针找中点：
- 快指针每次移动两步，慢指针每次移动一步
- 当快指针到达末尾时，慢指针恰好指向中点
- 注意处理偶数节点时中点的选择（代码中选择右半部分的第一个节点）
- 递归分割链表：
- 递归处理左半部分 head 到 slow
- 递归处理右半部分 slow.next 到末尾
- 合并有序链表：
- 创建虚拟头节点 dummy 和移动指针 tail
- 比较左右子链表当前节点值，将较小值的节点连接到 tail
- 处理剩余节点（其中一个子链表可能先遍历完）
时间复杂度：O (n log n) 空间复杂度：O (1)
var sortList = function(head) {if (!head || !head.next) return head;// 计算链表长度let length = 0;let node = head;while (node) {length++;node = node.next;}const dummy = new ListNode(0);dummy.next = head;// 按步长分割合并，步长从1开始每次翻倍for (let step = 1; step < length; step <<= 1) {let prev = dummy;let cur = dummy.next;while (cur) {// 分割出两个长度为step的子链表const left = cur;const right = split(left, step);cur = split(right, step);// 合并两个子链表prev.next = merge(left, right);// 移动prev指针到合并后的末尾while (prev.next) {prev = prev.next;}}}return dummy.next;
};// 辅助函数：分割出长度为n的链表，并返回剩余部分的头节点
function split(head, n) {while (head && --n) {head = head.next;}if (!head) return null;const rest = head.next;head.next = null;return rest;
}