遼寧城鄉(xiāng)建設(shè)部網(wǎng)站首頁(yè)網(wǎng)站策劃是干什么的

解題思路:兩種解法,一種優(yōu)先級(jí)隊(duì)列,一種分治
優(yōu)先級(jí)隊(duì)列解法:以節(jié)點(diǎn)中存儲(chǔ)的值進(jìn)行排序
依次遍歷所有的鏈表,把鏈表中的節(jié)點(diǎn)加入到優(yōu)先級(jí)隊(duì)列中
依次從優(yōu)先級(jí)隊(duì)列的彈出并刪除最小的元素加入到新的鏈表中,直到隊(duì)列為空,
返回新的鏈表
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;//防止出現(xiàn)循環(huán)鏈,a->b->areturn result.next;}
}
分治:類(lèi)似與歸并排序的思想
如果鏈表的長(zhǎng)度大于2:繼續(xù)對(duì)鏈表進(jìn)行拆分成兩部分,繼續(xù)使用分治的思想
將鏈表數(shù)組數(shù)組分成兩半,list[0,left]和list[left,end],分別對(duì)這對(duì)兩部分進(jìn)行分治排序合并,這兩部分排序后的結(jié)果first,second
然后對(duì)first和second這兩個(gè)鏈表進(jìn)行雙鏈表合并排序,合并思路:雙指針:因?yàn)閮蓚€(gè)鏈表有序,所以只需要依次比較兩個(gè)元素的大小,然后添加到新的鏈表中即可
first指針指向第一個(gè)鏈表,second指針指向第二個(gè)鏈表,result保存合并后的鏈表的頭節(jié)點(diǎn)的前驅(qū),tail初值指向result
如果fist和second當(dāng)前指向的節(jié)點(diǎn)都不為null,循環(huán)遍歷:
如果first.val<second.value,tail.next=first,first=first.next,tail=tail.next
否則,tail.next=second,second=second.next,tail=tail.next
循環(huán)結(jié)束之后,那么first和second只會(huì)有一個(gè)節(jié)點(diǎn)不為null,因?yàn)樵湵硪呀?jīng)有序,所以只需要將不為null的哪個(gè)鏈表添加到prev.next中即可
最終result.next即為合并后鏈表的第一個(gè)節(jié)點(diǎn)
如果鏈表的長(zhǎng)度等于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);}//對(duì)list[left,right]范圍的鏈表進(jìn)行合并,返回合并后新的鏈表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);//對(duì)左半部的鏈表分進(jìn)行分治合并,返回合并后的結(jié)果ListNode second = merge(lists,mid+1,right);//對(duì)右半部分的鏈表進(jìn)行分治合并,返回合并后的結(jié)果ListNode result = sortMerge(first,second);//對(duì)first和second進(jìn)行雙鏈表合并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;}
}