免费网站论坛,外贸流程英文版,安徽省建设工程信息网站6,线上营销平台有哪些#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 链表 归并排序 求解思路 实现代码 运行结果 共勉 题目链接
148. 排序链表
⛲ 题目描述
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
示例 1
输入head [4,2,1,3] 输出[1,2,3,4] 示例 2
输入head [-1,5,3,4,0] 输出[-1,0,3,4,5] 示例 3
输入head [] 输出[]
提示
链表中节点的数目在范围 [0, 5 * 104] 内 -105 Node.val 105
进阶你可以在 O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序吗 求解思路实现代码运行结果 ⚡ 链表 归并排序 求解思路
如果题目没有对于时间复杂度和空间复杂度的限制那么我们可以先额外开辟一个数组先来记录链表的数值然后排序后再次重新建立链表。但是如果按照该题目的限制要求在 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) {if (head null || head.next null)return head;ListNode left head, mid head.next, right head.next.next;while (right ! null right.next ! null) {left left.next;mid mid.next;right right.next.next;}// 断连left.next null;return merge(sortList(head), sortList(mid));}public ListNode merge(ListNode pHead1, ListNode pHead2) {// 一个已经为空了直接返回另一个if (pHead1 null)return pHead2;if (pHead2 null)return pHead1;// 加一个表头ListNode head new ListNode(0);ListNode cur head;// 两个链表都要不为空while (pHead1 ! null pHead2 ! null) {// 取较小值的结点if (pHead1.val pHead2.val) {cur.next pHead1;// 只移动取值的指针pHead1 pHead1.next;} else {cur.next pHead2;// 只移动取值的指针pHead2 pHead2.next;}// 指针后移cur cur.next;}// 哪个链表还有剩直接连在后面if (pHead1 ! null)cur.next pHead1;elsecur.next pHead2;// 返回值去掉表头return head.next;}}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
