境外网站搭建,discuz做资讯网站合适吗,无锡大型网站建设公司,博望网站建设148. 排序链表
题目#xff1a;给你链表的头结点 head #xff0c;请将其按升序排列并返回排序后的链表。
题目链接#xff1a; 148. 排序链表 时间复杂度#xff1a;快排 O(n^2) 超出时间限制
class Solution {public ListNode sortList(ListNode head) {if(headnull)…148. 排序链表
题目给你链表的头结点 head 请将其按升序排列并返回排序后的链表。
题目链接 148. 排序链表 时间复杂度快排 O(n^2) 超出时间限制
class Solution {public ListNode sortList(ListNode head) {if(headnull){return head;}ListNode dummynew ListNode(Integer.MIN_VALUE,null);ListNode pointnewdummy;ListNode pointoldhead;while(pointold!null){while(pointnew!nullpointnew.next!null){if(pointold.valpointnew.next.val){ListNode nextpointnew.next;ListNode nodenew ListNode(pointold.val);pointnew.nextnode;node.nextnext;pointnewdummy;break;}else{pointnewpointnew.next;}}if(pointnew.nextnull){ListNode nextpointnew.next;ListNode nodenew ListNode(pointold.val);pointnew.nextnode;node.nextnext;pointnewdummy;}pointoldpointold.next;}return dummy.next;}
}归并排序O(logn)
class Solution {public ListNode sortList(ListNode head) {if(headnull||head.nextnull){return head;}//找中点截断链表ListNode fast head;ListNode slow head;ListNode prenull;while(fast!nullfast.next!null){preslow;slowslow.next;fastfast.next.next;}//递归截断链表pre.nextnull;ListNode leftsortList(head);ListNode rightsortList(slow);//合并链表ListNode dummynew ListNode(0);ListNode res dummy;while (left ! null right ! null) {if (left.val right.val) {res.next left;left left.next;} else {res.next right;right right.next;}resres.next;}res.nextleft!null?left:right;return dummy.next;}
}归并排序迭代方法 时间复杂度O(logn)空间复杂度为O(1) 直接当作n个长度为1的链表进行归并 先归并为2个有序继而48…直到其长度大于链表长度n
public ListNode sortList(ListNode head) {if (head null || head.next null) {return head;}// 获取链表长度int length 0;ListNode current head;while (current ! null) {length;current current.next;}ListNode dummy new ListNode(0);dummy.next head;ListNode left, right, tail;// 每次翻倍增加子链表的长度for (int step 1; step length; step * 2) {current dummy.next;tail dummy;while (current ! null) {left current;right split(left, step); // 分割出两个子链表current split(right, step); //划分下一个lefttail merge(left, right, tail); // 合并两个子链表}}return dummy.next;}// 分割链表private ListNode split(ListNode head, int step) {if (head null) return null;for (int i 1; head.next ! null i step; i) {head head.next;}ListNode right head.next;head.next null;return right;}// 合并两个链表private ListNode merge(ListNode l1, ListNode l2, ListNode tail) {ListNode current tail;while (l1 ! null l2 ! null) {if (l1.val l2.val) {current.next l1;l1 l1.next;} else {current.next l2;l2 l2.next;}current current.next;}current.next (l1 ! null) ? l1 : l2;while (current.next ! null) {current current.next;}return current;}
