Commit5a934c1

authored

Merge pull requestTheAlgorithms#721 from pandeyarun709/MergeLinkedList

Add Merge K sorted LinkedList

2 parentsdbebab0 +4bc8396 commit5a934c1Copy full SHA for 5a934c1

File tree

+54

-0

lines changed

+54

-0

lines changed

Lines changed: 54 additions & 0 deletions

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

Comments

(0)