O(N lgK) 时间内合龙K个有序链表

O(N lgK) 时间内合并K个有序链表

问题：

在O(N lgK) 时间内合并K个有序链表， 这里N指的是K个链表中所有的元素个数。

分析：

这是一道非常经典的面试题，在很多大公司的面试题中，此题频繁出现。这题也是算法导论的作业题。

这题的思路如下：

1） 在每一个链表中取出第一个值，然后把它们放在一个大小为K的数组里，然后把这个数组当成heap，然后把该堆建成最小堆。此步骤的时间复杂度为O（K）

2 ）取出堆中的最小值（也是数组的第一个值），然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空（元素已经都被取出），则改变heap的大小。然后，执行MIN-HEAPIFY操作，此步骤的时间复杂度为O(lg K).

3 ） 不断的重复步骤二，直到所有的链表都为空。

代码如下：

public static void main(String[] args) {int k = 3;Node[] heads = new Node[k];Node n1 = new Node(1);Node n7 = new Node(7);Node n9 = new Node(9);Node n2 = new Node(2);Node n4 = new Node(4);Node n8 = new Node(8);Node n3 = new Node(3);Node n5 = new Node(5);Node n6 = new Node(6);n1.next = n7;n7.next = n9;n2.next = n4;n4.next = n8;n3.next = n5;n5.next = n6;heads[0] = n1;heads[1] = n2;heads[2] = n3;Test test = new Test();Node head = test.mergeKSortedList(heads);while(head != null) {System.out.println(head.data);head = head.next;}}
转载请注明出处：http://blog.csdn.net/beiyeqingteng