成都网站制作维护,wordpress 客户端管理,wordpress 显示选项打不开,越秀seo搜索引擎优化leetcode 148
思路
遍历链表并收集节点#xff1a;将链表中的每个节点断开其 next 指针后存入数组对数组进行排序#xff1a;使用 JavaScript 的内置 sort 方法对节点数组按值排序重新连接排序后的节点#xff1a;遍历排序后的数组#xff0c;依次连接每个节点形成新链表…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;
}
