余姚网站推广策划案,品牌宣传型网站建设方案,企业网站注册域名的步骤,小白怎么做跨境电商LeetCode#xff1a;排序链表
一、题目描述
给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
二、分析
这题咱们默认要求#xff1a;空间复杂度为O(1)。所以这把咱们用自底向上的方法实现归并排序#xff0c;则可以达到O(1) 的空间复杂…LeetCode排序链表
一、题目描述
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
二、分析
这题咱们默认要求空间复杂度为O(1)。所以这把咱们用自底向上的方法实现归并排序则可以达到O(1) 的空间复杂度。
具体算法如下
1、首先判断如果所给的 head 为 null 则返回null 2、求出所给链表head的长度length然后将链表拆分成子链表进行合并。具体算法如下
2.1、用subLen表示每次需要排序的子链表的长度初始值subLen为1.2.2、每次将链表拆分成若干个长度为subLen的子链表最后一个子链表的长度可以小于subLen按照每两个子链表一组进行合并通过使用合并两个有序链表的做法合并后即可得到若干个长度为 subLen2 的有序子链表最后一个子链表的长度可以小于 subLen2。合并两个子链表仍然使用合并两个有序链表的做法。2.3、将subLen的值加倍通过位运算左移1位的方式重复第2步对更长的有序子链表进行合并操作直到有序子链表的长度大于或等于length整个链表排序完毕。
如何保证每次合并后得到的子链表都是有序的呢可以通过数学归纳法证明。 1、初始时subLen为1每个长度为1的子链表都是有序的 2、如果每个长度为subLen的子链表已经有序那么合并两个长度为subLen的子链表后得到长度为subLen * 2 的子链表一定也是有序的。 3、当最后一个子链表的长度小于subLen时该子链表也是有序的合并两个链表之后得到的子链表一定也是有序的。
三、上代码
public class Deal11 {public ListNode sortList(ListNode head) {if (head null) {return null;}//1、从头向后遍历链表统计链表长度int length 0;ListNode p head;while(p ! null) {length;pp.next;}//2、设定result用于记录最终返回结果并对其进行最终的初始化ListNode result new ListNode(-1);result.next head;//3、将链表拆分成若干个长度为subLen的子链表并按照没两个子链表一组进行合并for (int subLen 1; subLen length; subLen 1) {//将subLen的值加倍通过位运算左移1位的方式ListNode pre result;ListNode cur result.next; //用于记录拆分链表的位置while (cur ! null) { //如果链表没有被拆完//3.1 拆分出链表1其长度为subLenListNode head_1 cur; //第一个链表的头即curfor (int i 1; i subLen cur ! null cur.next ! null; i) {cur cur.next;}//3.2 拆分出链表2其长度也为subLenListNode head_2 cur.next; //第二个链表的头即第一个链表尾部的下一个位置cur.next null; //断开第一个链表和第二个链表的连接cur head_2; //第二个链表的头重新赋给curfor (int i 1; i subLen cur ! null cur.next ! null; i) {cur cur.next;}//3.3 再次断开第二个链表的的连接ListNode next null;if (cur ! null) {next cur.next; //用于记录拆分完两个链表后结束的后序位置cur.next null;}//3.4 合并两个有序链表head_1 和 head_2ListNode merge mergeTwo(head_1, head_2);pre.next merge;while (pre.next ! null) {pre pre.next;}cur next;}}return result.next;}//合并两个有序链表public ListNode mergeTwo(ListNode head1, ListNode head2) {ListNode result new ListNode(-1);ListNode p result;ListNode p1 head1;ListNode p2 head2;while(p1 ! null p2 ! null) {if (p1.val p2.val) {p.next p2;p2 p2.next;} else {p.next p1;p1 p1.next;}p p.next;}if (p1 null) {p.next p2;}if (p2 null) {p.next p1;}return result.next;}
}
