leetcode(23):
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
思路:可以想到可以两两合并链表,循环一次,再两两合并(leetcode21),直到合并成一个。那么就可以想到用二分法,然后两两合并。当然如果可以,也可以用其他有规律的选择两两合并。
public class L23MergekSortedLists {
public static ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0){
return null;
}else if(lists.length == 1){
return lists[0];
}
int length = lists.length;
while(length > 1){
int mid = (length+1)/2;
for (int i = 0; i < length/2; i++) {
lists[i] = mergeTwoList(lists[i],lists[mid+1]);
}
length = mid;
}
return lists[0];
}
private static ListNode mergeTwoList(ListNode listNode, ListNode listNode2) {
if(listNode == null && listNode2 == null){
return null;
}else if(listNode == null){
return listNode2;
}else if(listNode2 == null){
return listNode;
}
ListNode head = new ListNode(0);
ListNode dummyHead = head;
while(listNode != null && listNode2 != null){
if(listNode.val >= listNode2.val){
head.next = listNode;
listNode = listNode.next;
}else {
head.next = listNode2;
listNode2 = listNode2.next;
}
head = head.next;
}
if(listNode != null){
head.next = listNode;
}
if(listNode2 != null){
head.next = listNode2;
}
return dummyHead.next;
}
}