片头制作网站,长安区建设局网站,贵州省建设厅住房和城乡建设官网二建考试,浙江义乌外发加工网文章目录题目描述思路 代码二刷题目描述
难点在于时空复杂度的要求
思路 代码
转化成#xff1a;归并排序 合并两个有序链表 即可利用快慢指针来拆分成两条链表注意#xff1a;链表的拆分 连接时间复杂度O(n * logn)#xff0c;空间复杂度 O(1)
/**…
文章目录题目描述思路 代码二刷题目描述
难点在于时空复杂度的要求
思路 代码
转化成归并排序 合并两个有序链表 即可利用快慢指针来拆分成两条链表注意链表的拆分 连接时间复杂度O(n * logn)空间复杂度 O(1)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode sortList(ListNode head) {if(head null || head.next null){return head;}// 1. 快慢指针分出前后两部分递归ListNode fast head;ListNode slow head;while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;}// 长度为2的情况特殊考虑if(slow.next null){slow head;}// 拆解递归 O(logn)fast sortList(slow.next);slow.next null;slow sortList(head);// 2. 返回值进行合并(转化成合并链表)return mergeSortedList(slow, fast);}// 链表合并O(n)ListNode mergeSortedList(ListNode head1, ListNode head2){if(head1 null){return head2;}if(head2 null){return head1;}if(head1.val head2.val){head1.next mergeSortedList(head1.next, head2);return head1;}else{head2.next mergeSortedList(head1, head2.next);return head2;}}
}二刷
好吧…记得思路是快慢指针 合并有序链表但是具体咋写确实回想不起来 其实就是两个函数快慢指针二分链表 合并两个有序链表双重递归
class Solution {// 1. 快慢指针二分链表public ListNode sortList(ListNode head) {if(head null || head.next null) {return head;}ListNode slow head, fast head;while(fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}// 两个的情况避免无限循环if(slow.next null) {slow head;}fast sortList(slow.next);slow.next null;slow sortList(head);return mergeSort(slow, fast);}// 2. 合并两个有序链表 O(n)、O(1)public ListNode mergeSort(ListNode headA, ListNode headB) {if(headB null) {return headA;}if(headA null) {return headB;}if(headA.val headB.val) {headA.next mergeSort(headA.next, headB);return headA;}else {headB.next mergeSort(headA, headB.next);return headB;}}
}
