Commitf3ef5b6

committed

Add Merge K sorted LinkedList

1 parentc14af04 commitf3ef5b6Copy full SHA for f3ef5b6

File tree

+63

-0

lines changed

+63

-0

lines changed

Lines changed: 63 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,63 @@`
	`1`	`+importjava.util.*;`
	`2`	`+`
	`3`	`+publicclassMerge_K_SortedLinkedlist {`
	`4`	`+`
	`5`	`+/*`
	`6`	`+ * This function merge K sorted LinkedList`
	`7`	`+ * @param Node []a : array of LinkedList`
	`8`	`+ * @param int N : size of array`
	`9`	`+ *`
	`10`	`+ * author Arun Pandey (https://github.com/pandeyarun709)`
	`11`	`+ */`
	`12`	`+NodemergeKList(Node[]a,intN)`
	`13`	`+ {`
	`14`	`+// Min Heap`
	`15`	`+PriorityQueue<Node>min =newPriorityQueue<>(newComparator<Node>(){`
	`16`	`+`
	`17`	`+publicintcompare(Nodex ,Nodey){`
	`18`	`+returnx.data -y.data;`
	`19`	`+ }`
	`20`	`+ });`
	`21`	`+`
	`22`	`+// adding head of all linkedList in min heap`
	`23`	`+for(inti =0 ;i<N ;i++)`
	`24`	`+ {`
	`25`	`+min.add(a[i]);`
	`26`	`+ }`
	`27`	`+`
	`28`	`+// Make new head among smallest heads in K linkedList`
	`29`	`+Nodehead =min.poll();`
	`30`	`+min.add(head.next);`
	`31`	`+Nodecurr =head;`
	`32`	`+`
	`33`	`+//merging LinkedList`
	`34`	`+while(!min.isEmpty()) {`
	`35`	`+`
	`36`	`+Nodetemp =min.poll();`
	`37`	`+curr.next =temp;`
	`38`	`+curr =temp;`
	`39`	`+`
	`40`	`+//Add Node in min Heap only if temp.next is not null`
	`41`	`+if(temp.next !=null){`
	`42`	`+min.add(temp.next);`
	`43`	`+ }`
	`44`	`+ }`
	`45`	`+`
	`46`	`+returnhead;`
	`47`	`+`
	`48`	`+`
	`49`	`+ }`
	`50`	`+`
	`51`	`+// Node Class`
	`52`	`+privateclassNode{`
	`53`	`+privateintdata;`
	`54`	`+privateNodenext;`
	`55`	`+`
	`56`	`+publicNode(intd)`
	`57`	`+ {`
	`58`	`+this.data =d;`
	`59`	`+next =null;`
	`60`	`+ }`
	`61`	`+ }`
	`62`	`+`
	`63`	`+}`

Comments

(0)