Day 31, 23, Merge k Sorted Lists

Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
--------------------------------------------------------------
Solution #1 O(k*n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *merge2Lists (ListNode *l1, ListNode *l2) {
        ListNode *ret,*cur;
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val < l2->val) {
            ret = l1;
            cur = l1;
            l1 = l1->next;
        }else {
            ret = l2;
            cur = l2;
            l2 = l2->next;
        }
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }else {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if (l1 == NULL) {
            cur->next = l2;
        }else {
            cur->next = l1;
        }
        return ret;
    }
    

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (lists.size() == 0) return NULL;
        ListNode *ret = lists[0];
        for (int i=1;i<lists.size();i++) {
            ret = merge2Lists(ret,lists[i]);
        }
        return ret;
    }
};

Solution #2, O（nlogk）, using Priority Queue
note struct of comparison function and declaration of priority queue

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct comp{
        bool operator()(const ListNode* n1, const ListNode* n2){
            return n1->val > n2->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        priority_queue<ListNode*,vector<ListNode*>,comp> heap;
        ListNode *ret=NULL,*cur;
        for (int i=0;i<lists.size();i++) {
            if (lists[i] != NULL) {
                heap.push(lists[i]);
            }
        }
        
        while (!heap.empty()) {
            ListNode *min = heap.top();
            heap.pop();
            if (ret == NULL) {
                ret = min;
                cur = min;
            }else {
                cur->next = min;
                cur = cur->next;
            }
            if (min->next != NULL) {
                heap.push(min->next);
            }
        }
        return ret;
    }
};

Update on Sep-11-2014
Solution #3, push all nodes in priority_queue, then output will be in order

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct cmp {
        bool operator()(const ListNode* l1, const ListNode* l2) {
            return l1->val > l2->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *dummy = new ListNode(INT_MIN);
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        bool flag = true;
        
        while (flag) {
            flag = false;
            for (int i = 0; i < lists.size(); i++) {
                if (lists[i] != NULL) {
                    flag = true;
                    heap.push(lists[i]);
                    lists[i] = lists[i]->next;
                }
            }
        }
        
        ListNode *head = dummy;
        while (!heap.empty()) {
            ListNode *t = heap.top();
            head->next = t;
            heap.pop();
            head = t;
        }
        head->next = NULL; // prevent infinite loop
        
        return dummy->next;
    }
};

Solution #4, merge all pairs of two adjacent lists for each iteration. O(nlog(k)), n is the total elements from all lists
Update on Nov-26-2014

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *merge2Lists (ListNode *l1, ListNode *l2) {
        ListNode *ret,*cur;
        if (l1 == NULL) {
            return l2;
        }
        if (l2 == NULL) {
            return l1;
        }
        if (l1->val < l2->val) {
            ret = l1;
            cur = l1;
            l1 = l1->next;
        }else {
            ret = l2;
            cur = l2;
            l2 = l2->next;
        }
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }else {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if (l1 == NULL) {
            cur->next = l2;
        }else {
            cur->next = l1;
        }
        return ret;
    }

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (lists.size() == 0) return NULL;
        
        int size = lists.size();    
        while (size != 1) {
            
            for (int i = 0; i < size; i = i + 2) {
                if (i + 1 < size) {
                    lists[i / 2] = merge2Lists(lists[i],lists[i + 1]);
                }else{
                    lists[i / 2] = lists[i];
                }
            }
            size = size / 2 + size % 2;
        }
        
        return lists[0];
    }
};

与上面同样思路，但是用递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0), *itr = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val > l2->val) {
                itr->next = l2;
                l2 = l2->next;
                itr = itr->next;
            }else {
                itr->next = l1;
                l1 = l1->next;
                itr = itr->next;
            }
        }
        
        if (l1 == NULL) {
            itr->next = l2;
        }
        if (l2 == NULL) {
            itr->next = l1;
        }
        return dummy->next;
    }

    ListNode* helper(vector<ListNode*> &lists,int start,int end) {
        if (start > end) return NULL;
        if (start == end) return lists[start];
        int mid = (start + end) / 2;
        ListNode *l1 = helper(lists,start,mid);
        ListNode *l2 = helper(lists,mid + 1,end);
        return mergeTwoLists(l1,l2);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return helper(lists,0,lists.size() - 1);
    }
};

Java, 用priority queue
时间O(N * log k), 空间为O(k), N为总node的个数，k为list的数量。
先把所有的头指针插入到queue，然后一个个pop。把刚pop出来的node的一下个，推回queue

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue que = new PriorityQueue<>((a, b) -> {
            return a.val - b.val;
        });
                
        for (ListNode node : lists) {
            if (node != null) que.add(node);
        }
        
        ListNode dummy = new ListNode(0);
        ListNode itr = dummy;

        while (!que.isEmpty()) {
            ListNode next = que.poll();
            if (next.next != null) que.add(next.next);
            itr.next = next;
            itr = next;
        }
        
        return dummy.next;
    }
}

如果可以重复利用原来的array的话，空间可以算是O(1)

/**
 * 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 == null || lists.length == 0) return null;
        List rt = Arrays.asList(lists);
        while (rt.size() != 1) {
            rt = divide(rt);
        }
        
        return rt.get(0);
    }
    
    private List divide(List lists) {
        int n = lists.size();
        List rt = new ArrayList<>();
        for (int i = 0; i < n / 2; i++) {
            rt.add(mergeTwo(lists.get(i), lists.get(n - 1 - i)));
        }
        
        if (n % 2 == 1) rt.add(lists.get(n / 2));
        
        return rt;
    }
    
    private ListNode mergeTwo(ListNode node1, ListNode node2) {
        
        if (node1 == null) return node2;
        if (node2 == null) return node1;
            
        ListNode dummy = new ListNode(0);
        ListNode itr;
        if (node1.val > node2.val) {
            dummy.next = node2;
            node2 = node2.next;
        }else {
            dummy.next = node1;
            node1 = node1.next;
        }
        itr = dummy.next;
        
        while (node1 != null && node2 != null) {
            
            if (node1.val > node2.val) {
                itr.next = node2;
                itr = node2;
                node2 = node2.next;
            }else {
                itr.next = node1;
                itr = node1;
                node1 = node1.next;
            }
        }
        
        if (node1 != null) {
            itr.next = node1;
        }
        if (node2 != null) {
            itr.next = node2;
        }
        
        return dummy.next;
    }
}