question:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
Ideas:
//链表
public static ListNode mergeKLists(ListNode[] lists){
if(lists==null || lists.length<1)
return null;
ListNode head = new ListNode(-1);
ListNode phead =head;
int count=0,index=0,min; //奇数已经遍历完的链表
while(count<lists.length){
//找出K个链表的头结点值最小的那一个
count=0;
min = Integer.MAX_VALUE;
for(int i=0;i<lists.length;i++){
if(lists[i]==null){
count++;
continue;
}
if(lists[i].val<min){
min = lists[i].val;
index=i;
}
}
if(count==lists.length)
break;
phead.next=lists[index];
phead=phead.next;
lists[index]=lists[index].next;
}
return head.next;
}
方案二
//优先队列
public static ListNode mergeKLists2(ListNode[] lists){
ListNode head = new ListNode(-1);
ListNode phead = head;
//构造优先队列
Queue<ListNode> minheap = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
if(o1.val<o2.val)
return -1;
else if(o1.val==o2.val)
return 0;
else {
return 1;
}
}
}); //初始化优先队列
for(ListNode l:lists){
if(l!=null)
minheap.add(l);
}
while(!minheap.isEmpty()){
phead.next=minheap.poll(); //队列的头元素必为所有链表头元素中的最小值
phead=phead.next;
if(phead.next!=null)
minheap.add(phead.next);
}
return head.next;
}
方案三
//归并类似
public static ListNode mergeKLists3(ListNode[] lists){
int length=lists.length;
int inteval=1;
while(inteval<length){
for(int i=0;i<length-inteval;i+=inteval*2){
lists[i] = mergeTwoLists(lists[i],lists[i+inteval]);
}
inteval *=2;
}
return lists[0];
}
网友评论