Merge pull request TheAlgorithms#721 from pandeyarun709/MergeLinkedList

yanglbme · web-flow · commit 5a934c17c439 · 2019-03-20T16:24:37.000+08:00
Add Merge K sorted LinkedList
diff --git a/DataStructures/Lists/Merge_K_SortedLinkedlist.java b/DataStructures/Lists/Merge_K_SortedLinkedlist.java
@@ -0,0 +1,54 @@
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+/**
+ * @author Arun Pandey (https://github.com/pandeyarun709)
+ */
+public class Merge_K_SortedLinkedlist {
+
+    /**
+     * This function merge K sorted LinkedList
+     *
+     * @param a array of LinkedList
+     * @param N size of array
+     * @return node
+     */
+    Node mergeKList(Node[] a, int N) {
+        // Min Heap
+        PriorityQueue<Node> min = new PriorityQueue<>(Comparator.comparingInt(x -> x.data));
+
+        // adding head of all linkedList in min heap
+        min.addAll(Arrays.asList(a).subList(0, N));
+
+        // Make new head among smallest heads in K linkedList 
+        Node head = min.poll();
+        min.add(head.next);
+        Node curr = head;
+
+        // merging LinkedList
+        while (!min.isEmpty()) {
+
+            Node temp = min.poll();
+            curr.next = temp;
+            curr = temp;
+
+            // Add Node in min Heap only if temp.next is not null
+            if (temp.next != null) {
+                min.add(temp.next);
+            }
+        }
+
+        return head;
+    }
+
+    private class Node {
+        private int data;
+        private Node next;
+
+        public Node(int d) {
+            this.data = d;
+            next = null;
+        }
+    }
+}
