【Leetcode刷题篇】leetcode148 排序链表
发布日期:2021-06-29 15:33:52
浏览次数:2
分类:技术文章
本文共 1275 字,大约阅读时间需要 4 分钟。
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
归并排序
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode sortList(ListNode head) { return mergeSort(head,null); } public ListNode mergeSort(ListNode head,ListNode tail){ // 截止条件 if(head==null){ return null; } if(head.next==tail){ head.next = null; return head; } // 找mid // 快慢指针 ListNode slow = head,fast = head; while(fast!=tail&&fast.next!=tail){ slow = slow.next; fast = fast.next.next; } ListNode mid = slow; ListNode left = mergeSort(head,mid); ListNode right = mergeSort(mid,tail); ListNode sorted = merge(left,right); return sorted; } // 合并两个有序链表 public ListNode merge(ListNode head1,ListNode head2){ ListNode dummy = new ListNode(-1); ListNode pre = dummy; while(head1!=null&&head2!=null){ if(head1.val
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109904196 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月20日 01时18分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
未来属于人工智能工程师,但成功转型不容易
2019-04-29
科技界“挠头”:困扰科技界可持续发展的难题
2019-04-29
标准出现问题,人工智能正在走向错误的方向
2019-04-29
不论何时,互联网从业者一直幸福着~
2019-04-29
架构师知识体系全景图
2019-04-29
guava中EventBus(事件总线)源码分析与使用
2019-04-29
程序员成神之路文章目录
2019-04-29
最全架构设计实践方法论: 微服务
2019-04-29
linux入门--磁盘管理之分区、格式化与挂载
2019-04-29
开发必备:HTTP 及 TLS
2019-04-29
如何设计自己的第一个加密交易机器人?
2019-04-29
TKDE 2020 | 综述:基于知识图谱的推荐系统
2019-04-29
在后台的python:众多程序员无法攻克的难题
2019-04-29
国会大厦骚乱,与一家极不可靠的面部识别公司……
2019-04-29
电动汽车的“专属危险”:网络威胁问题不容小觑
2019-04-29
统治50年:为什么SQL在如今仍然很重要?
2019-04-29
测试是一场竞争,而数据每次都会获得胜利
2019-04-29
复工之后:员工如何改善网络安全?
2019-04-29
2020-10-27
2019-04-29
2021-03-29
2019-04-29