python云服务器网站开发实例,外贸小家电网站推广,公司做的网站搜索不到,公众号取名简单大气题目描述
给你链表的头结点head#xff0c;请将其按照升序排列并返回排序后的链表。
解答一#xff1a;使用递归法进行归并排序
分割环节#xff1a;找到当前链表的中点#xff0c;并从中点将链表断开以方便在下次递归的时候cut#xff0c;链表的片段拥有正确的边界我们…题目描述
给你链表的头结点head请将其按照升序排列并返回排序后的链表。
解答一使用递归法进行归并排序
分割环节找到当前链表的中点并从中点将链表断开以方便在下次递归的时候cut链表的片段拥有正确的边界我们使用fast slow快慢双指针算法奇数个节点找到中点偶数个节点找到中心节点左边的节点这时候快指针走到结束位置。 public ListNode sortList(ListNode head) {return head null ? null : mergeSort(head);}private ListNode mergeSort(ListNode head){if(head.next null){return head;}ListNode p head,q head , pre null;while(q ! null q.next ! null){pre p;p p.next;q q.next.next;}//找到中点之后执行slow.next null 将链表切断pre.next null;//将链表切割成左半部分和右半部分//head是左半部分//p是我们右半部分的开始ListNode l mergeSort(head);ListNode r mergeSort(p);return merge(l,r);}ListNode merge(ListNode l,ListNode r){//合并就可以了ListNode dummyHead new ListNode(0);ListNode cur dummyHead;while(l ! null r ! null){if(l.val r.val){cur.next l;cur cur.next;l l.next;}else{cur.next r;cur cur.next;r r.next;}}if(l ! null){cur.next l;}if(r ! null){cur.next r;}return dummyHead.next;}}
