首页 > 代码库 > LeetCodeMerge k Sorted Lists
LeetCodeMerge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
对每一个排序链表都设置一个指针。每次讲指针指向的单元中最小值链接,直到所有指针为空。
public class Solution {
public ListNode mergeKLists(List<ListNode> lists) {
int length = lists.size();
if(length == 0)return null;
int num = 0;
while(num<length)
{
if(lists.get(num)!=null)
break;
num++;
}
if(num == length)return null;
ListNode[] start = new ListNode[length];
int minIndex = 0;
int min = Integer.MAX_VALUE;
for(int i=0;i<length;i++)
{
start[i] = lists.get(i);
if(start[i]!=null&&start[i].val<min)
{
minIndex = i;
min = start[i].val;
}
}
ListNode head = lists.get(minIndex);
ListNode node = head;
start[minIndex] = start[minIndex].next;
while(!isAllEnd(start))
{
findMin(start,node);
node = node.next;
}
return head;
}
public void findMin(ListNode[] lists,ListNode node)
{
int min = Integer.MAX_VALUE;
int minIndex = 0;
for(int i=0;i<lists.length;i++)
{
if(lists[i]!=null&&lists[i].val<min)
{
min = lists[i].val;
minIndex = i;
}
}
node.next = lists[minIndex];
lists[minIndex] = lists[minIndex].next;
}
public boolean isAllEnd(ListNode[] lists)
{
int length = lists.length;
int i = 0;
while(i<length)
{
if(lists[i] != null)
{
return false;
}
i++;
}
return true;
}
}