题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
import java.util.*; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public void quickSort(ListNode[] arr,int k){ quick(arr,0,k-1); } public void quick(ListNode[] arr,int left,int right){ if(left>=right){ return; } int privot=parttion(arr,left,right); quick(arr,left,privot-1); quick(arr,privot+1,right); } private int parttion(ListNode[] arr,int left,int right){ ListNode priovt=arr[left]; while(left<right){ while(left<right&&arr[right].val>=priovt.val){ right--; } arr[left]=arr[right]; while(left<right&&arr[left].val<=priovt.val){ left++; } arr[right]=arr[left]; } arr[left]=priovt; return left; } public boolean isfull(ListNode[] arr,int k){ return k==arr.length; } public ListNode mergeKLists(ArrayList<ListNode> lists) { ListNode ret=null; int len=lists.size(); ListNode[] arr=new ListNode[10]; int k=0; for(int i=0;i<len;i++){ ListNode cur=lists.get(i); while(cur!=null){ if(isfull(arr,k)){ arr=Arrays.copyOf(arr,arr.length*2); } arr[k]=cur; k++; cur=cur.next; } } for(int i=0;i<k;i++){ arr[i].next=null; } quickSort(arr,k); ret=arr[0]; ListNode cur=ret; for(int i=1;i<k;i++){ cur.next=arr[i]; cur=cur.next; } return ret; } }