Tuesday, February 3, 2015

LeetCode [23] Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct Comp
{
    bool operator()(ListNode *a, ListNode *b)
    {
        return a->val > b->val;
    }
};

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<ListNode *, vector<ListNode *>, Comp> pq;
        for (int i = 0; i < lists.size(); ++i)
        {
            if(lists[i]) pq.push(lists[i]);
        }
        ListNode *Head = new ListNode(0);
        ListNode *p = Head;
        while(!pq.empty())
        {
            ListNode *l = pq.top();
            pq.pop();
            p->next = l;
            p = p->next;
            if(l->next) pq.push(l->next);
        }
        return Head->next;
    }
};

class Solution {
    ListNode *divide(vector<listnode *> &lists, int a, int b){
        if(a>b) return NULL;
        if(a==b) return lists[a];
        int m=(a+b)/2;
        ListNode *la = divide(lists, a, m);
        ListNode *lb = divide(lists, m+1, b);
        return merge(la, lb);
    }

    ListNode *merge(ListNode *la, ListNode *lb){
        ListNode *sentinel = new ListNode(0);
        ListNode *p = sentinel;
        while(la && lb){
            if(la->val<=lb->val){
                p->next = la;
                la = la->next;
            }else{
                p->next = lb;
                lb = lb->next;
            }
            p = p->next;
        }
        if(la) p->next = la;
        if(lb) p->next = lb;
        return sentinel->next;
    }
public:
    ListNode *mergeKLists(vector<listnode *> &lists) {
        ListNode * sentinel = NULL;
        return divide(lists, 0, lists.size()-1);
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
        ListNode H = new ListNode();
        ListNode p = H;
        int n = lists.length;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b)->a.val-b.val);    
        for(ListNode node : lists) if(node!=null) pq.add(node);
    
        while(!pq.isEmpty()){
            ListNode node = pq.poll();
            p.next = node;
            p = p.next;
            if(node.next!=null) pq.add(node.next);
        }

        return H.next;
    }
}
at

No comments:

Post a Comment