题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param lists ListNode类ArrayList * @return ListNode类 */ public ListNode mergeKLists (ArrayList<ListNode> lists) { // write code here return divdeMearge(0,lists.size()-1,lists); } protected ListNode divdeMearge(int left,int right,ArrayList<ListNode> lists){ if(left> right) return null; if(left==right){ return lists.get(left); } int mid=(left+right)/2; return merge(divdeMearge(left,mid,lists),divdeMearge(mid+1,right,lists)); } protected ListNode merge(ListNode leftlist,ListNode rightlist){ if(leftlist==null) return rightlist; if(rightlist==null) return leftlist; ListNode dummpy=new ListNode(0); ListNode res=dummpy; while(leftlist!=null&&rightlist!=null){ if(leftlist.val<rightlist.val){ dummpy.next=leftlist; leftlist=leftlist.next; } else{ dummpy.next=rightlist; rightlist=rightlist.next; } dummpy=dummpy.next; } if(leftlist==null) dummpy.next=rightlist; if(rightlist==null) dummpy.next=leftlist; return res.next; } }