法律咨询东莞网站建设,网站维护服务费,宁波谷歌seo,it培训学校解题思路#xff1a;两种解法#xff0c;一种优先级队列#xff0c;一种分治优先级队列解法#xff1a;以节点中存储的值进行排序依次遍历所有的链表#xff0c;把链表中的节点加入到优先级队列中依次从优先级队列的弹出并删除最小的元素加入到新的链表中#xff0c;直到…解题思路两种解法一种优先级队列一种分治优先级队列解法以节点中存储的值进行排序依次遍历所有的链表把链表中的节点加入到优先级队列中依次从优先级队列的弹出并删除最小的元素加入到新的链表中直到队列为空返回新的链表AC代码class Solution {public static ListNode mergeKLists(ListNode[] lists) {PriorityQueueListNode queue new PriorityQueueListNode((first,second)-first.val-second.val);for (ListNode list : lists) {while (list!null){queue.add(list);listlist.next;}}ListNode result new ListNode();ListNode tem result;while (queue.size()!0){ListNode node queue.remove();tem.next node;temtem.next;}tem.nextnull;//防止出现循环链a-b-areturn result.next;}
}分治类似与归并排序的思想如果链表的长度大于2继续对链表进行拆分成两部分继续使用分治的思想将链表数组数组分成两半list[0,left]和list[left,end]分别对这对两部分进行分治排序合并,这两部分排序后的结果firstsecond然后对first和second这两个链表进行双链表合并排序合并思路双指针因为两个链表有序所以只需要依次比较两个元素的大小然后添加到新的链表中即可first指针指向第一个链表second指针指向第二个链表result保存合并后的链表的头节点的前驱tail初值指向result如果fist和second当前指向的节点都不为null循环遍历如果first.valsecond.valuetail.nextfirstfirstfirst.nexttailtail.next否则tail.nextsecondsecondsecond.nexttailtail.next循环结束之后那么first和second只会有一个节点不为null因为原链表已经有序所以只需要将不为null的哪个链表添加到prev.next中即可最终result.next即为合并后链表的第一个节点如果链表的长度等于1不需要分治合并直接返回该链表即可AC代码class Solution {public static ListNode mergeKLists(ListNode[] lists) {if (listsnull||lists.length0){return null;}return merge(lists,0,lists.length-1);}//对list[left,right]范围的链表进行合并返回合并后新的链表public static ListNode merge(ListNode[] lists,int left,int right){if (leftright){return lists[left];}int mid (leftright)/2;ListNode first merge(lists,left,mid);//对左半部的链表分进行分治合并返回合并后的结果ListNode second merge(lists,mid1,right);//对右半部分的链表进行分治合并返回合并后的结果ListNode result sortMerge(first,second);//对first和second进行双链表合并return result;}public static ListNode sortMerge(ListNode first,ListNode second){ListNode result new ListNode();ListNode tail result;while (first!nullsecond!null){if (first.valsecond.val){tail.next first;firstfirst.next;}else {tail.nextsecond;secondsecond.next;}tail tail.next;}tail.next(firstnull)?second:first;return result.next;}
}
