遼寧城鄉(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;}
}