辽宁城乡建设部网站首页网站建设推广多少钱

解题思路:两种解法,一种优先级队列,一种分治
优先级队列解法:以节点中存储的值进行排序
依次遍历所有的链表,把链表中的节点加入到优先级队列中
依次从优先级队列的弹出并删除最小的元素加入到新的链表中,直到队列为空,
返回新的链表
AC代码:
class Solution {public static ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((first,second)->first.val-second.val);for (ListNode list : lists) {while (list!=null){queue.add(list);list=list.next;}}ListNode result = new ListNode();ListNode tem = result;while (queue.size()!=0){ListNode node =queue.remove();tem.next =node;tem=tem.next;}tem.next=null;//防止出现循环链,a->b->areturn result.next;}
}
分治:类似与归并排序的思想
如果链表的长度大于2:继续对链表进行拆分成两部分,继续使用分治的思想
将链表数组数组分成两半,list[0,left]和list[left,end],分别对这对两部分进行分治排序合并,这两部分排序后的结果first,second
然后对first和second这两个链表进行双链表合并排序,合并思路:双指针:因为两个链表有序,所以只需要依次比较两个元素的大小,然后添加到新的链表中即可
first指针指向第一个链表,second指针指向第二个链表,result保存合并后的链表的头节点的前驱,tail初值指向result
如果fist和second当前指向的节点都不为null,循环遍历:
如果first.val<second.value,tail.next=first,first=first.next,tail=tail.next
否则,tail.next=second,second=second.next,tail=tail.next
循环结束之后,那么first和second只会有一个节点不为null,因为原链表已经有序,所以只需要将不为null的哪个链表添加到prev.next中即可
最终result.next即为合并后链表的第一个节点
如果链表的长度等于1:不需要分治合并,直接返回该链表即可
AC代码:
class Solution {public static ListNode mergeKLists(ListNode[] lists) {if (lists==null||lists.length==0){return null;}return merge(lists,0,lists.length-1);}//对list[left,right]范围的链表进行合并,返回合并后新的链表public static ListNode merge(ListNode[] lists,int left,int right){if (left==right){return lists[left];}int mid = (left+right)/2;ListNode first = merge(lists,left,mid);//对左半部的链表分进行分治合并,返回合并后的结果ListNode second = merge(lists,mid+1,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!=null&&second!=null){if (first.val<second.val){tail.next= first;first=first.next;}else {tail.next=second;second=second.next;}tail = tail.next;}tail.next=(first==null)?second:first;return result.next;}
}