【链表】合并k个以排序的链表(归并排序)_暮色_年华的博客-CSDN博客
相当于合并n个有序的单链表,且每个单链表长度为1。
把单链表每个加在list中,然后套用归并排序的函数。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// write code here
if(head==null)return null;
ArrayListlist=new ArrayList<>();
ListNode p=head;
while(p!=null){
ListNode q=p.next;
p.next=null;
list.add(p);
p=q;
}
return mergeKLists(list);
}
public ListNode merge(ListNode l1,ListNode l2){
if(l1==null||l2==null){
return l1==null?l2:l1;
}
ListNode dummyNode=new ListNode(-1);
ListNode cur=dummyNode;
while(l1!=null&&l2!=null){
if(l1.val lists,int L,int R){
if(L==R){
return lists.get(L);
}
if(L>R)return null;
int mid=L+((R-L)>>1);
return merge(mergeList(lists,L,mid),mergeList(lists,mid+1,R));
}
public ListNode mergeKLists(ArrayList lists) {
return mergeList(lists,0,lists.size()-1);
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)