Screenshot from 2016-01-23 15:58:48.png
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
else if (lists.length == 1)
return lists[0];
return divide(lists, 0, lists.length - 1);
}
private ListNode divide(ListNode[] lists, int begin, int end) {
if (end - begin + 1 < 2)
return lists[begin];
int middle = (begin + end) / 2;
ListNode left = divide(lists, begin, middle);
ListNode right = divide(lists, middle + 1, end);
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null)
return l2;
else if (l2 == null)
return l1;
ListNode dummy = new ListNode(-1);
ListNode temp = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
temp.next = l1;
l1 = l1.next;
}
else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
temp.next = (l1 == null) ? l2 : l1;
return dummy.next;
}
}
我就是采用了merge sort 的思想，把這些lists先divide丹弱，到只剩下兩個的時候德撬，再merge一下。算了下復雜度躲胳，其實挺高的蜓洪。每個list都需要重復訪問多次把。
比如0, 1, 2, 3 條list
那么 0 ,1 merge坯苹， 2 和3 merge
然后 0,1組成的綜合體與2,3組成的綜合體再merge
這個時候又需要訪問下0,1,2,3隆檀。 有重復。時間復雜度應該比較高。雖然看測試下來刚操，效果還不錯。
后來看了一個新的解法再芋，復雜度要低很多菊霜。用priority queue 來做。
My code:
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
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;
}
});
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null)
pq.add(lists[i]);
}
ListNode dummy = new ListNode(-1);
ListNode scanner = dummy;
while (pq.size() > 0) {
ListNode temp = pq.poll();
scanner.next = temp;
scanner = scanner.next;
if (temp.next != null)
pq.add(temp.next);
}
return dummy.next;
}
}
具體看下代碼就懂了济赎。復雜度是 log(k) * n
k = number of lists
n = number of all nodes
注意下這道題目用到了 PrioirtyQueue 這個數據結構鉴逞，并且可以自帶Comparator進去。
記得上次使用到的數據結構司训， TreeSet, 其實就是Binary search tree
參考網站：
http://www.programcreek.com/2013/02/leetcode-merge-k-sorted-lists-java/
Anyway, Good luck, Richardo!
My code:
import java.util.PriorityQueue;
import java.util.Comparator;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(8, new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
pq.offer(lists[i]);
}
}
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
while (!pq.isEmpty()) {
ListNode curr = pq.poll();
if (curr.next != null) {
pq.offer(curr.next);
}
pre.next = curr;
pre = curr;
}
return dummy.next;
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println("111");
}
}
how to initialize a PriorityQueue object
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(8, new Comparator<Integer>() {
public int compare(Integer i1, Integer i2) {
return i1.compareTo(i2);
}
});
覺得用pq 來做這道題目是最好的构捡。
Anyway, Good luck, Richardo! -- 09/14/2016
