山东电力建设第三工程公司网站,做网站类的网站,icp是什么,江苏中禾建设网站目录 题目描述#xff1a;148. 排序链表#xff08;中等#xff09;题目接口解题思路代码 PS: 题目描述#xff1a;148. 排序链表#xff08;中等#xff09;
给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
LeetCode做题链接#xff1… 目录 题目描述148. 排序链表中等题目接口解题思路代码 PS: 题目描述148. 排序链表中等
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
LeetCode做题链接LeetCode-排序链表
示例 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(nlog 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) {}
}解题思路
参考题解Sort List 归并排序链表
思路递归
1.用二分法的方法将列表从中间分割再把分割的列表继续从中间分割分割到最小单位快慢指针2.递归终止条件 当 head.next None 时说明只有一个节点了直接返回此节点3.再返回两个分割列表的合并列表合并有序列表 可以跟着这个图理解一下~
代码
/*** 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) {// 1、递归结束条件if (head null || head.next null) {return head;}// 2、找到链表中间节点并断开链表 递归下探ListNode midNode middleNode(head);ListNode rightHead midNode.next;// 截断列表midNode.next null;// 递归不断下探到最深出最低端再合并返回ListNode left sortList(head);ListNode right sortList(rightHead);// 3、当前层业务操作合并有序链表return mergeTwoLists(left, right);}// 找到链表中间节点876. 链表的中间结点private ListNode middleNode(ListNode head) {if (head null || head.next null) {return head;}ListNode slow head;ListNode fast head.next.next;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}return slow;}// 合并两个有序链表21. 合并两个有序链表private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode sentry new ListNode(-1);ListNode curr sentry;while(l1 ! null l2 ! null) {if(l1.val l2.val) {curr.next l1;l1 l1.next;} else {curr.next l2;l2 l2.next;}curr curr.next;}curr.next l1 ! null ? l1 : l2;return sentry.next;}
}PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
