MergeKSortedLists23

fluency03 · fluency03 · commit f74220c2dbfe · 2018-03-11T23:15:06.000+01:00
diff --git a/src/MergeKSortedLists23.java b/src/MergeKSortedLists23.java
@@ -110,4 +110,59 @@ private ListNode mL(ListNode[] lists, int l, int r) {
         return dmHead.next;
     }
 
+
+    public ListNode mergeKLists4(ListNode[] lists) {
+        if (lists == null || lists.length == 0) return null;
+        ListNode dummy = new ListNode(0);
+        ListNode p = dummy;
+        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>((l1, l2) -> Integer.compare(l1.val, l2.val));
+        for (ListNode node: lists) {
+            if (node != null) q.add(node);
+        }
+        while (!q.isEmpty()) {
+            ListNode curr = q.poll();
+            if (curr.next != null) q.add(curr.next);
+            curr.next = null;
+            p.next = curr;
+            p = p.next;
+        }
+
+        return dummy.next;
+    }
+
+
+    public ListNode mergeKLists5(ListNode[] lists) {
+        if (lists == null || lists.length == 0) return null;
+
+        int len = lists.length;
+        int interval = 1;
+        while (interval < len) {
+            for (int i=0; i < len-interval; i+=interval*2)
+                lists[i] = mergeTwoLists5(lists[i], lists[i + interval]);
+            interval *= 2;
+        }
+
+        return lists[0];
+    }
+
+    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
+        ListNode dummy = new ListNode(0);
+        ListNode p = dummy;
+        while (l1 != null && l2 != null) {
+            if (l1.val >= l2.val) {
+                p.next = l2;
+                l2 = l2.next;
+            } else {
+                p.next = l1;
+                l1 = l1.next;
+            }
+            p = p.next;
+            p.next = null;
+        }
+        if (l1 != null) p.next = l1;
+        if (l2 != null) p.next = l2;
+        return dummy.next;
+    }
+
+
 }
diff --git a/src/MergeTwoSortedLists21.java b/src/MergeTwoSortedLists21.java
@@ -43,10 +43,10 @@ public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
         if (l2 == null) return l1;
 
         if (l1.val >= l2.val) {
-            l2.next = mergeTwoLists(l1, l2.next);
+            l2.next = mergeTwoLists2(l1, l2.next);
             return l2;
         } else {
-            l1.next = mergeTwoLists(l1.next, l2);
+            l1.next = mergeTwoLists2(l1.next, l2);
             return l1;
         }
     }

Original file line number	Diff line number	Diff line change
`@@ -43,10 +43,10 @@ public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {`
`43`	`43`	`if (l2 == null) return l1;`
`44`	`44`
`45`	`45`	`if (l1.val >= l2.val) {`
`46`		`- l2.next = mergeTwoLists(l1, l2.next);`
	`46`	`+ l2.next = mergeTwoLists2(l1, l2.next);`
`47`	`47`	`return l2;`
`48`	`48`	`} else {`
`49`		`- l1.next = mergeTwoLists(l1.next, l2);`
	`49`	`+ l1.next = mergeTwoLists2(l1.next, l2);`
`50`	`50`	`return l1;`
`51`	`51`	`}`
`52`	`52`	`}`