1 题目
LeetCode第23题,合并k个有序的链表.
2 暴力法
直接遍历所有链表,取出所有节点的值,用数组存储,非降序排序,然后创建一个新链表用头插法依次插入节点.
List<Integer> s = new ArrayList<>();
for(ListNode x:lists)
{
while(x != null)
{
s.add(x.val);
x = x.next;
}
}
s.sort((a,b) -> {return a.compareTo(b);});
ListNode result = new ListNode(0);
ListNode t = result;
for(Integer x:s)
{
t.next = new ListNode(x);
t = t.next;
}
return result.next;
这里要注意一下,sort那里不能写成:
s.sort((a,b)->{return a>b ? 1 : -1;});
没有考虑到等于的情况,所以用compareTo代替:
s.sort((a,b)->{return a.compareTo(b);});
3 直接合并法
每次遍历所有链表,取出首节点的值,各个比较然后得出最小值,将最小值插入新链表,然后移动最小值所在的链表的指针,直到所有链表为空.
ListNode result = new ListNode(0);
ListNode t = result;
int len = lists.length;
int nullNodeNums = 0;
for(boolean [] b = new boolean[len];nullNodeNums<len;)
{
int min = Integer.MAX_VALUE;
int minIndex = -1;
for(int index = 0;index<len;++index)
{
ListNode x = lists[index];
if(x == null)
{
if(!b[index])
{
b[index] = true;
++nullNodeNums;
}
}
else if(x.val < min)
{
min = x.val;
minIndex = index;
}
}
if(minIndex != -1)
{
t.next = new ListNode(min);
t = t.next;
lists[minIndex] = lists[minIndex].next;
}
}
return result.next;
这里使用了一个布尔数组判断是否某个节点已经移动到尾部,即表示是否为空,为空的话跳过这个节点,不为空的话取其值,计算是否为最小值.得到最小值后,添加到结果节点中,并移动最小值所在链表的指针.
这个方法看起来慢得很啊.
4 优先队列
优先队列是上两个方法的结合,遍历所有节点,取值并根据其值确定优先级添加到优先队列中,然后依次出队,将出队的值直接插入到新链表中.
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(ListNode x:lists)
{
while(x != null)
{
queue.add(x.val);
x = x.next;
}
}
ListNode s = new ListNode(0);
ListNode t = s;
while(!queue.isEmpty())
{
t.next = new ListNode(queue.poll());
t = t.next;
}
return s.next;
java的优先队列可以直接add即可,按照默认出队序列(对于整数是小的先出)使用尾插法插入到新链表中.
嗯,好像还可以的样子,但是还是不够快.
5 两两合并法
合并k个链表,相当于合并2个链表k-1次,利用递归的思想,每次合并两个链表,将合并后的链表后返回作为下一个要合并的链表继续合并.
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
ListNode t = lists[0];
for(int i=1;i<lists.length;++i)
t = merge(t, lists[i]);
return t;
}
//public ListNode merge(ListNode a,ListNode b)
merge为直接合并两个链表的操作,不难,就不贴代码了,首先赋值t为第一个链表,然后依次合并t与剩下的n-1个链表.
好慢啊.
6 分治法
分治法是两两合并法的改进,两两合并每次合并两个链表,分治法每次合并一半数量的链表,总体思想是这样的:想要得到最终有序的链表,若左半部分的链表与右半部分的链表都有序,则相当于合并两个有序链表,为了得到左半部分的有序链表,需要继续对左半部分进行一半的分割,再次分成左半部分与右半部分,然后再分,直到某部分只有一个链表,然后返回,以合并两个普通有序链表的方式合并两个返回的链表.
public ListNode f(int start,int end)
{
int len = end - start;
if(len <= 1)
return lists[start];
ListNode l = f(start,start+len/2);
ListNode r = f(start+len/2,end);
return merge(l, r);
}
代码非常简洁,一开始为判断递归的条件,区间长度小于等于1直接返回[start]的节点,然后递归合并左半部分与右半部分的节点.
一个字,舒服.
真快.