网站建设 图片问题,找能做网站的,网站建设费一般摊销几年,公司网站打不开是什么原因题目#xff1a; 给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
解法一#xff1a; 递归解法#xff0c;自顶向下 链表版二路归并排序#xff08;升序#xff0c;递归版#xff09;#xff0c;稳定排序 时间复杂度…题目 给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
解法一 递归解法自顶向下 链表版二路归并排序升序递归版稳定排序 时间复杂度为 On*logn空间复杂度递归栈的深度 Ologn 首先用快慢指针找到中心节点以中心节点为左链表最后节点、递归左右俩链表直到链表长度小于等于 1 回溯 回溯时是将俩有序链表合并成一个有序链表合并后将头尾嵌回原链表然后继续回溯 注意不能以 null 位结尾需要判断 tail 为结尾最后要将排序好的链表头尾嵌回原链表注意它是稳定排序处理 特别注意由于回溯合并链表后老的 head 位置改变因此再次回溯决不能使用 head 判断而是使用 virtual.next 才是正确头结点当然也可以返回 newHead 节点 代码一 /*** 链表版二路归并排序升序递归版稳定排序* 时间复杂度为 On*logn空间复杂度递归栈的深度 Ologn*/private ListNode solution(ListNode head) {// 判空if (head null || head.getNext() null) {return head;}// 添加虚拟节点指向头结点方便处理ListNode virtual new ListNode(0, head);// 递归版归并排序核心算法recursionMergeSort(virtual, head, null);return virtual.getNext();}/*** 首先用快慢指针找到中心节点以中心节点为左链表最后节点、递归左右俩链表直到链表长度小于等于 1 回溯* 回溯时是将俩有序链表合并成一个有序链表合并后将头尾嵌回原链表然后继续回溯* 注意不能以 null 位结尾需要判断 tail 为结尾最后要将排序好的链表头尾嵌回原链表注意它是稳定排序处理* 特别注意由于回溯合并链表后老的 head 位置改变因此再次回溯决不能使用 head 判断而是使用 virtual.next 才是正确头结点* param virtual 当前链表头结点前一个节点* param head 当前链表头结点* param tail 当前链表尾结点后一个节点*/private void recursionMergeSort(ListNode virtual, ListNode head, ListNode tail) {// 小于等于 1 个节点回溯注意结尾为 tailif (head tail || head.getNext() tail) {return;}// 快慢指针找到中心节点ListNode mid getMidNode(virtual, tail);
// System.out.println(head: head);
// System.out.println(mid: mid);
// System.out.println(tail: tail \n);// 递归左右俩链表recursionMergeSort(virtual, head, mid.getNext());recursionMergeSort(mid, mid.getNext(), tail);// 左右俩有序链表合并成一个有序链表返回新的头尾节点
// System.out.println(head: head);
// System.out.println(mid: mid);
// System.out.println(tail: tail \n);// 注意不能用使用回溯的 headListNode[] newNodes mergeTwoSortedLinked(virtual.getNext(), mid.getNext(), tail);ListNode newHead newNodes[0];ListNode newPreTail newNodes[1];// 头尾节点嵌回原链表virtual.setNext(newHead);newPreTail.setNext(tail);
// System.out.println(virtual: virtual);
// System.out.println(newHead: newHead);
// System.out.println(newPreTail: newPreTail \n);}/*** 左右俩有序链表合并成一个有序链表返回新的头尾节点* param lHead 第一个链表头结点* param rHead 第一个链表尾结点后一个节点同时也是第二个链表的头结点* param rTail 第二个链表尾结点后一个节点* return 新的头尾节点0-新头结点1-新尾结点*/private ListNode[] mergeTwoSortedLinked(ListNode lHead, ListNode rHead, ListNode rTail) {ListNode newVirtual new ListNode();ListNode newPreTail newVirtual;ListNode l lHead;ListNode r rHead;while (l ! rHead || r ! rTail) {if (l rHead) {newPreTail.setNext(r);newPreTail r;r r.getNext();} else if (r rTail) {newPreTail.setNext(l);newPreTail l;l l.getNext();// 注意稳定排序规则} else if (l.getVal() r.getVal()) {newPreTail.setNext(l);newPreTail l;l l.getNext();} else {newPreTail.setNext(r);newPreTail r;r r.getNext();}}ListNode[] newNodes new ListNode[2];newNodes[0] newVirtual.getNext();newNodes[1] newPreTail;return newNodes;}/*** 快慢指针找到中心节点* param virtual 头结点前一个节点* param tail 尾结点后一个节点* return 中心节点*/private ListNode getMidNode(ListNode virtual, ListNode tail) {ListNode slow virtual;ListNode fast virtual;while (fast ! tail fast.getNext() ! tail) {slow slow.getNext();fast fast.getNext().getNext();}return slow;}解法二 链表版二路归并排序升序迭代版自底向上稳定排序 时间复杂度为 On*logn空间复杂度O1 先获取链表长度然后分割成多组每组连续俩节点排序可看做两个有序链表因为只有一个节点合并成一个链表注意最后一组可能不满 接着连续四个节点排序同样是两个有序链表合并成一个链表然后连续八个、十六个…直到排好序个数大于等于链表长度就完成 注意链表每次排序后需要嵌回原链表
代码二 /*** 链表版二路归并排序升序迭代版自底向上稳定排序* 时间复杂度为 On*logn空间复杂度O1*/private ListNode solutionOptimization(ListNode head) {// 判空if (head null || head.getNext() null) {return head;}// 迭代版二路归并核心算法return iterationMergeSort(head);}/*** 先获取链表长度然后分割成多组每组连续俩节点排序可看做两个有序链表因为只有一个节点合并成一个链表注意最后一组可能不满* 接着连续四个节点排序同样是两个有序链表合并成一个链表然后连续八个、十六个...直到排好序个数大于等于链表长度就完成* 注意链表每次排序后需要嵌回原链表* return 返回排好序的新的头节点*/private ListNode iterationMergeSort(ListNode head) {// 获取链表长度int len getLinkedLen(head);System.out.println(len: len \n);// 头结点前添加虚拟节点方便操作ListNode virtual new ListNode(0, head);// 循环操作连续两个节点、四个节点、八个节点...for (int group 2; group / 2 len; group * 2) {// 第一个链表头结点前一个节点ListNode left virtual;System.out.println(left: left);// 每 group 个元素一组前 group/2 个与后 group/2 个有序链表合并成一个有序链表int halfGroup group / 2;for (int now 0; now len; now group) {System.out.println(String.format(now:%s group:%s left:%s, now, group, left));// 从第 now 位开始最多到 len 长度连续 group 个链表进行合并然后 left 后移到下一组每组头结点的前一个节点left mergeContinueLinked(group, halfGroup, now, len, left, left.getNext());}System.out.println();}return virtual.getNext();}/*** 获取链表长度*/private int getLinkedLen(ListNode head) {int len 0;while (head ! null) {len;head head.getNext();}return len;}/*** 从第 now 位开始最多到 len 长度连续 group 个链表进行合并然后 left 后移* param group 每组个数* param halfGroup 半组长度其为排好序的长度* param now 当前下标模拟数组* param len 链表总长度* param preHead 当前链表起点位置的前一个节点* param lHead 当前链表起点位置* return lHead 接下来移到的位置的前一个节点*/private ListNode mergeContinueLinked(int group, int halfGroup, int now, int len, ListNode preHead, ListNode lHead) {// 后续不足 halfGroup 个元素代表均已排if (len now halfGroup) {return null;}// 第一个链表尾结点后一个节点同时也是第二个链表头结点ListNode rHead moveBack(lHead, halfGroup);// 第二个链表尾结点后一个节点ListNode rTail moveBack(rHead, halfGroup);System.out.println(String.format(lHead:%s rHead:%s rTail:%s, lHead, rHead, rTail));// 合并俩有序链表ListNode[] newNodes mergeTwoSortedLinked2(lHead, rHead, rTail);ListNode newHead newNodes[0];ListNode newPreTail newNodes[1];// 合并后的有序链表嵌回原链表preHead.setNext(newHead);newPreTail.setNext(rTail);System.out.println(String.format(preHead:%s newPreTail:%s, preHead, newPreTail) \n);return newPreTail;}/*** head 开始后移 halfGroup 个元素其中移动到 null 则不用再移动了*/private ListNode moveBack(ListNode head, int halfGroup) {while (head ! null halfGroup 0) {halfGroup--;head head.getNext();}return head;}/*** 左右俩有序链表合并成一个有序链表返回新的头尾节点* param lHead 第一个链表头结点* param rHead 第一个链表尾结点后一个节点同时也是第二个链表的头结点* param rTail 第二个链表尾结点后一个节点* return 新的头尾节点0-新头结点1-新尾结点*/private ListNode[] mergeTwoSortedLinked2(ListNode lHead, ListNode rHead, ListNode rTail) {ListNode newVirtual new ListNode();ListNode newPreTail newVirtual;ListNode l lHead;ListNode r rHead;while (l ! rHead || r ! rTail) {if (l rHead) {newPreTail.setNext(r);newPreTail r;r r.getNext();} else if (r rTail) {newPreTail.setNext(l);newPreTail l;l l.getNext();// 保证排序稳定性} else if (l.getVal() r.getVal()) {newPreTail.setNext(l);newPreTail l;l l.getNext();} else {newPreTail.setNext(r);newPreTail r;r r.getNext();}}ListNode[] newNodes new ListNode[2];newNodes[0] newVirtual.getNext();newNodes[1] newPreTail;return newNodes;}
