首页 > 代码库 > leetcode : merge k sorted list
leetcode : merge k sorted list
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
两种方法：
（1） 类似于归并排序，把链表数组分割成两两最小的链表对（可能存在落单的情况，要做处理）， 再调用merge two sorted lists 方法
（2） 类似于堆排序的思路。 （尚未实践）。 comparator priorityqueue
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null){
return null;
}
return mergeLists(lists,0,lists.length - 1);
}
public ListNode mergeLists(ListNode[] lists,int start, int end){
if(lists == null || lists.length == 0){
return null;
}
if(start == end){
return lists[start];
}
int mid = start + (end - start) / 2;
ListNode left = mergeLists(lists,start,mid);
ListNode right = mergeLists(lists,mid + 1,end);
return mergeTwoLists(left,right);
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
if(l1 == null && l2 == null){
return null;
}
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 != null){
cur.next = l1;
}
if(l2 != null){
cur.next = l2;
}
return dummy.next;
}
}
leetcode : merge k sorted list
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。