23. 合并K个排序链表
1.想法
不能每一个都进行比较那么比较合适是的归并排序
每次都两两合并,和归并排序的流程一样
2.代码
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0)return null;
ListNode result = mergeMyKLists(lists,0,lists.length-1);
return result;
}
private ListNode mergeMyKLists(ListNode[] lists, int left, int right) {
if(left==right)return lists[left];
//分左右两个ListNode
ListNode leftNodes = mergeMyKLists(lists, left, (right - left) / 2 + left);
ListNode rightNodes = mergeMyKLists(lists, (right - left) / 2 + left + 1, right);
//合并左右两个ListNode
if(leftNodes == null)return rightNodes;
if(rightNodes == null)return leftNodes;
ListNode newNode = null;
if(leftNodes.val<rightNodes.val){
newNode = new ListNode(leftNodes.val);
leftNodes = leftNodes.next;
}else{
newNode = new ListNode(rightNodes.val);
rightNodes = rightNodes.next;
}
ListNode newHead = newNode;
while(leftNodes!=null&&rightNodes!=null){
if(leftNodes.val<rightNodes.val){
newHead.next=new ListNode(leftNodes.val);
leftNodes = leftNodes.next;
}else{
newHead.next=new ListNode(rightNodes.val);
rightNodes = rightNodes.next;
}
newHead = newHead.next;
}
if(leftNodes!=null){
newHead.next = leftNodes;
}
if(rightNodes!=null){
newHead.next = rightNodes;
}
return newNode;
}
网友评论