石柱网站制作,石家庄建站软件,上海建筑企业资质查询平台,WordPress怎么找主题方法1:插入方法进行改进
class Solution {public ListNode sortList(ListNode head) {/*想法#xff1a;设置两个指针first,last分别指向当前有序子链表的头和尾节点#xff1b;并遍历链表#xff0c;当遍历到的节点值大于last的值时#xff0c;就将该节点插入到有序子链表…方法1:插入方法进行改进
class Solution {public ListNode sortList(ListNode head) {/*想法设置两个指针first,last分别指向当前有序子链表的头和尾节点并遍历链表当遍历到的节点值大于last的值时就将该节点插入到有序子链表表尾值小于first时插入到子链表表头处于二者中间时就遍历进行插入*/if(head null)return null;ListNode first head,last head;ListNode p head.next;head.next null;while(p ! null){ListNode temp p.next;if(p.val last.val){//插入表尾last.next p;p.next null;last p;}else if(p.val first.val){//插入表头p.next first;first p;}else{// 遍历进行插入for(ListNode q first;q ! last ;q q.next){if(q.next.val p.val){p.next q.next;q.next p;break;}}} p temp;}return first;}
}
方法2:自顶向下的归并排序
归并排序的时间复杂度问题在每一层中进行寻找中间节点有序链表进行两两合并都需要2n,而归并排序总共会进行logn层处理因此最终的时间复杂度就是O(nlogn)。
class Solution {public ListNode sortList(ListNode head) {/*自顶向下的归并排序首先寻找中间节点在利用归并排序将当前需要排序的链表进行两两分别排序最后在通过合并两个有序链表的方式以及递归的方式进行排序。*/if(head null)return null;return sortSubList(head,null);}//将链表进行排序(tail指向)public ListNode sortSubList(ListNode head,ListNode tail){if(head.next null)return head;if(head.next tail){head.next null;return merge(head,tail);}//先找到链表的中间节点ListNode slow head,fast head.next.next;while(fast ! tail){slow slow.next;fast fast.next;if(fast ! tail)fast fast.next;}//将左边的子链表表尾指向空指针右边子链表表尾本就是空指针ListNode subHead2 slow.next;slow.next null;ListNode head1 sortSubList(head,slow);ListNode head2 sortSubList(subHead2,tail);return merge(head1,head2);}//将两个子链表进行排序并合并返回合并后的链表头节点//判断是否到了尾,即是否到了空节点即可public ListNode merge(ListNode head1,ListNode head2){ListNode head new ListNode(-1,null); ListNode temp head,temp1 head1,temp2 head2;while(temp1 ! null temp2 ! null){if(temp1.val temp2.val){temp.next temp1;temp1 temp1.next;}else{temp.next temp2;temp2 temp2.next;}temp temp.next;}while(temp1 ! null){temp.next temp1;temp1 temp1.next;temp temp.next;}while(temp2 ! null){temp.next temp2;temp2 temp2.next;temp temp.next;}return head.next;}
} 方法3自底向上的归并排序
class Solution {public ListNode sortList(ListNode head) {/*自顶向下的归并排序首先寻找中间节点在利用归并排序将当前需要排序的链表进行两两分别排序最后在通过合并两个有序链表的方式以及递归的方式进行排序。*/if(head null)return null;//遍历链表获取链表长度int length 0;ListNode p head;while(p ! null){length;p p.next;}ListNode hair new ListNode(-1,head);for(int subLength 1;subLength length;subLength * 2){//开始遍历链表获取子链表并两两合并ListNode pre hair, cur hair.next;while(cur ! null){//获取一个的子链表ListNode head1 cur;for(int i 1;i subLength cur.next !null;i){cur cur.next;}ListNode head2 cur.next;cur.next null;cur head2;//再获取一个子链表for(int i 1;i subLength cur!null;i){cur cur.next;}if(cur ! null){ListNode temp cur.next;cur.next null;cur temp;}ListNode mergeResult merge(head1,head2);//pre指针指向当前两个子链表的前面的一个节点pre.next mergeResult;while(pre.next ! null)pre pre.next;}}return hair.next;}//将两个子链表进行排序并合并返回合并后的链表头节点//判断是否到了尾,即是否到了空节点即可public ListNode merge(ListNode head1,ListNode head2){ListNode head new ListNode(-1,null); ListNode temp head,temp1 head1,temp2 head2;while(temp1 ! null temp2 ! null){if(temp1.val temp2.val){temp.next temp1;temp1 temp1.next;}else{temp.next temp2;temp2 temp2.next;}temp temp.next;}while(temp1 ! null){temp.next temp1;temp1 temp1.next;temp temp.next;}while(temp2 ! null){temp.next temp2;temp2 temp2.next;temp temp.next;}return head.next;}
}
