Merge k Sorted Lists, Leetcode 解题笔记

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

这道题一句话,却是一道难题。现在看到注明”hard”的题就心虚,这可怎么办啊。。。
理解题意后第一想法是每次比较所有list的head们,选最小的加到solution list上,不过这方法太费时了,时间复杂度是O(kn^2)。

参考别人的答案,发现利用priority queue的方法是最简单的,代码注释很详细,这里不多说了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists.size() == 0) return null;
        
        //create the priority queue, override the compare method in Comparator.
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(), 
            new Comparator<ListNode>(){
                public int compare(ListNode a, ListNode b){
                    return a.val - b.val;
                }
            }
        );
        
        //add head of each list to the priority queue
        for(int i = 0; i < lists.size(); i++){
            if(lists.get(i) != null){
                q.add(lists.get(i));
            }
        }
        
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(q.size()>0){
            ListNode temp = q.poll();
            cur.next = temp;
            if(temp.next != null)
                q.add(temp.next);
            cur = cur.next;
        }
        return head.next;
    }
}

还有另一种解法,是利用merge sort,实现起来稍微复杂,但时间复杂度与上一种方法一样,都是O(knlogn)。以下代码是直接copy别人的,没有实际测试。

public class Solution {
    public ListNode mergeKLists(List&amp;lt;ListNode&amp;gt; lists) {
        if (lists.size() == 0)
            return null;
        return mergeKLists(lists, 0, lists.size() - 1);
    }
    
    public ListNode mergeKLists(List&amp;lt;ListNode&amp;gt; lists, int left, int right) {
        if (left &amp;lt; right) {
            int mid = (left + right) / 2;
            return merge(mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right));
        }
        return lists.get(left);
    }
    
    public ListNode merge(ListNode m, ListNode n) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (m != null &amp;amp;&amp;amp; n != null) {
            if (m.val &amp;lt; n.val) {
                p.next = m;
                p = p.next;
                m = m.next;
            } else {
                p.next = n;
                p = p.next;
                n = n.next;
            }
        }
        if (m != null)
            p.next = m;
        else
            p.next = n;
        return head.next;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s