feat: add 023

Blankj · Blankj · commit f9dd130aa420 · 2017-10-15T20:07:25.000+08:00
diff --git a/README.md b/README.md
@@ -72,6 +72,7 @@
 |:------------- |:------------- |:------------- |
 |4|[Median of Two Sorted Arrays][004]|Array, Binary Search, Divide and Conquer|
 |10|[Regular Expression Matching][010]|String, Dynamic Programmin, Backtracking|
+|23|[Merge k Sorted Lists][023]|Linked List, Divide and Conquer, Heap|
 
 
 
@@ -124,3 +125,4 @@
 
 [004]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md
 [010]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/010/README.md
+[023]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/023/README.md
diff --git a/note/023/README.md b/note/023/README.md
@@ -0,0 +1,101 @@
+# [Merge k Sorted Lists][title]
+
+## Description
+
+Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
+
+**Tags:** Linked List, Divide and Conquer, Heap
+
+
+## 思路0
+
+题意是合并多个已排序的链表，分析并描述其复杂度，我们可以用分治法来两两合并他们，假设`k`为总链表个数，`N`为总元素个数，那么其时间复杂度为`O(Nlogk)`。
+
+``` java
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode mergeKLists(ListNode[] lists) {
+        if (lists.length == 0) return null;
+        return helper(lists, 0, lists.length - 1);
+    }
+
+    private ListNode helper(ListNode[] lists, int left, int right) {
+        if (left >= right) return lists[left];
+        int mid = left + right >>> 1;
+        ListNode l0 = helper(lists, left, mid);
+        ListNode l1 = helper(lists, mid + 1, right);
+        return merge2Lists(l0, l1);
+    }
+
+    private ListNode merge2Lists(ListNode l0, ListNode l1) {
+        ListNode node = new ListNode(0), tmp = node;
+        while (l0 != null && l1 != null) {
+            if (l0.val <= l1.val) {
+                tmp.next = new ListNode(l0.val);
+                l0 = l0.next;
+            } else {
+                tmp.next = new ListNode(l1.val);
+                l1 = l1.next;
+            }
+            tmp = tmp.next;
+        }
+        tmp.next = l0 != null ? l0 : l1;
+        return node.next;
+    }
+}
+```
+
+## 思路1
+
+还有另一种思路是利用优先队列，该数据结构用到的是堆排序，所以对总链表个数为`k`的复杂度为`logk`，总元素为个数为`N`的话，其时间复杂度也为`O(Nlogk)`。
+
+``` java
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode mergeKLists(ListNode[] lists) {
+        if (lists.length == 0) return null;
+        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
+            @Override
+            public int compare(ListNode o1, ListNode o2) {
+                if (o1.val < o2.val) return -1;
+                else if (o1.val == o2.val) return 0;
+                else return 1;
+            }
+        });
+        ListNode node = new ListNode(0), tmp = node;
+        for (ListNode l : lists) {
+            if (l != null) queue.add(l);
+        }
+        while (!queue.isEmpty()) {
+            tmp.next = queue.poll();
+            tmp = tmp.next;
+            if (tmp.next != null) queue.add(tmp.next);
+        }
+        return node.next;
+    }
+}
+```
+
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
+
+
+
+[title]: https://leetcode.com/problems/merge-k-sorted-lists
+[ajl]: https://github.com/Blankj/awesome-java-leetcode
diff --git a/src/com/blankj/hard/_010/Solution.java b/src/com/blankj/hard/_010/Solution.java
@@ -1,10 +1,10 @@
-package com.blankj.easy._010;
+package com.blankj.hard._010;
 
 /**
  * <pre>
  *     author: Blankj
  *     blog  : http://blankj.com
- *     time  : 2017/04/24
+ *     time  : 2017/10/13
  *     desc  :
  * </pre>
  */
diff --git a/src/com/blankj/hard/_023/Solution.java b/src/com/blankj/hard/_023/Solution.java
@@ -0,0 +1,75 @@
+package com.blankj.hard._023;
+
+import com.blankj.structure.ListNode;
+
+import java.util.Comparator;
+import java.util.PriorityQueue;
+
+/**
+ * <pre>
+ *     author: Blankj
+ *     blog  : http://blankj.com
+ *     time  : 2017/10/15
+ *     desc  :
+ * </pre>
+ */
+public class Solution {
+//    public ListNode mergeKLists(ListNode[] lists) {
+//        if (lists.length == 0) return null;
+//        return helper(lists, 0, lists.length - 1);
+//    }
+//
+//    private ListNode helper(ListNode[] lists, int left, int right) {
+//        if (left >= right) return lists[left];
+//        int mid = left + right >>> 1;
+//        ListNode l0 = helper(lists, left, mid);
+//        ListNode l1 = helper(lists, mid + 1, right);
+//        return merge2Lists(l0, l1);
+//    }
+//
+//    private ListNode merge2Lists(ListNode l0, ListNode l1) {
+//        ListNode node = new ListNode(0), tmp = node;
+//        while (l0 != null && l1 != null) {
+//            if (l0.val <= l1.val) {
+//                tmp.next = new ListNode(l0.val);
+//                l0 = l0.next;
+//            } else {
+//                tmp.next = new ListNode(l1.val);
+//                l1 = l1.next;
+//            }
+//            tmp = tmp.next;
+//        }
+//        tmp.next = l0 != null ? l0 : l1;
+//        return node.next;
+//    }
+
+    public ListNode mergeKLists(ListNode[] lists) {
+        if (lists.length == 0) return null;
+        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
+            @Override
+            public int compare(ListNode o1, ListNode o2) {
+                if (o1.val < o2.val) return -1;
+                else if (o1.val == o2.val) return 0;
+                else return 1;
+            }
+        });
+        ListNode node = new ListNode(0), tmp = node;
+        for (ListNode l : lists) {
+            if (l != null) queue.add(l);
+        }
+        while (!queue.isEmpty()) {
+            tmp.next = queue.poll();
+            tmp = tmp.next;
+            if (tmp.next != null) queue.add(tmp.next);
+        }
+        return node.next;
+    }
+
+    public static void main(String[] args) {
+        Solution solution = new Solution();
+        ListNode.print(solution.mergeKLists(new ListNode[]{
+                ListNode.createTestData("[1,3,5,7]"),
+                ListNode.createTestData("[2,4,6]")
+        }));
+    }
+}
