遼寧城鄉(xiāng)建設(shè)部網(wǎng)站首頁網(wǎng)站策劃是干什么的
解題思路：兩種解法，一種優(yōu)先級隊列，一種分治
優(yōu)先級隊列解法：以節(jié)點中存儲的值進行排序
依次遍歷所有的鏈表，把鏈表中的節(jié)點加入到優(yōu)先級隊列中
依次從優(yōu)先級隊列的彈出并刪除最小的元素加入到新的鏈表中，直到隊列為空，
返回新的鏈表
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;}
}分治：類似與歸并排序的思想
如果鏈表的長度大于2：繼續(xù)對鏈表進行拆分成兩部分，繼續(xù)使用分治的思想
將鏈表數(shù)組數(shù)組分成兩半，list[0,left]和list[left,end]，分別對這對兩部分進行分治排序合并,這兩部分排序后的結(jié)果first，second
然后對first和second這兩個鏈表進行雙鏈表合并排序，合并思路：雙指針：因為兩個鏈表有序，所以只需要依次比較兩個元素的大小，然后添加到新的鏈表中即可
first指針指向第一個鏈表，second指針指向第二個鏈表，result保存合并后的鏈表的頭節(jié)點的前驅(qū)，tail初值指向result
如果fist和second當(dāng)前指向的節(jié)點都不為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只會有一個節(jié)點不為null，因為原鏈表已經(jīng)有序，所以只需要將不為null的哪個鏈表添加到prev.next中即可
最終result.next即為合并后鏈表的第一個節(jié)點
如果鏈表的長度等于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);//對左半部的鏈表分進行分治合并，返回合并后的結(jié)果ListNode second = merge(lists,mid+1,right);//對右半部分的鏈表進行分治合并，返回合并后的結(jié)果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;}
}