leetcode 077. 链表排序 JavaScript
2022/8/3 14:23:57
本文主要是介绍leetcode 077. 链表排序 JavaScript,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
// 剑指 Offer II 077. 链表排序 /** * @param {ListNode} head * @return {ListNode} */ var sortList = function (head) { // 1. 首先判断当前链表不存在 ,或链表只有一个节点,则直接返回 head if (!head || !head.next) { return head; } // 2. 获取分割的右侧链表 let rightLists = split(head); // 3. 获取分割的左侧链表, 当获取到右侧链表后,会将链表断开,从而剩余 head 为 左侧链表 let leftLists = head; // 4. 返回合并并排序后的链表 return mergeList(sortList(leftLists), sortList(rightLists)); }; // 排序并合并左右链表 function mergeList(leftLists, rightLists) { // 创建一个空的链表 let res = new ListNode(); // 复制一份当前空的链表 let temp = res; // 判断左侧链表存在,且左右链表也存在 while (leftLists !== null && rightLists !== null) { // 如果左侧链表值小于右侧链表值 if (leftLists.val <= rightLists.val) { // 将空链表的下一个节点指向值小的链 res.next = leftLists; // 左侧链表指针向后移动一位,继续遍历 leftLists = leftLists.next; } else if (leftLists.val > rightLists.val) { // 否则当右侧链表节点值小,同理,将小值赋值给 res res.next = rightLists; // 右侧链表指针后移一位 rightLists = rightLists.next; } // 同时,每次循环,将新创建的链表的指针后移一位,为了连接下一个节点 res = res.next; } // 如果循环结束,左侧链表不为 null,说明左侧链表有剩余,拼接左侧链表 if (leftLists !== null) { res.next = leftLists; } // 如果循环结束,右侧链表不为 null,说明右侧链表有剩余,拼接右侧链表 if (rightLists !== null) { res.next = rightLists; } // 返回创建链表的 next,因为第一个节点没有值 return temp.next; } // 分割链表为左右链表 function split(head) { // 使用快慢指针循环 let slow = head; let fast = head.next; // 当快指针指向最后一个节点时,慢指针刚好指向中间的节点 while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; } // 断开 head 指针下一个节点 let lists = slow.next; slow.next = null; // 返回慢指针指向的节点的下一个,即为分割后的右侧链表 return lists; }
参考链接
这篇关于leetcode 077. 链表排序 JavaScript的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?