Merge k Sorted Lists

Description

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Example
Given lists:
[
  2->4->null,
  null,
  -1->null
],
return -1->2->4->null.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        if (lists.empty()) {
            return nullptr;
        }
        int n = lists.size()-1;
        // Solution 1 - my own
        helper(lists, 0, n);
        return lists[0];
        // Solution 1-1
        // return divide_conquer(lists, 0, n);
    }
private:
    // ----------------------------------------------------------------------- 
    // Solution 1 - raw 
    // firstly, merge the first/last, second/second last until i j meets
    //          the scale has been half
    // Secondly, repeat the first step until we get only one list "start == end"
    // Finally, O(n * averageLen(List))
    void helper(vector<ListNode*> &lists, int start, int end) {
        if (start == end) {
            return;
        }
        int i = start;
        int j = end;
        for (; i < j; ++i, --j) {
            lists[i] = mergetwo(lists[i], lists[j]);
        }
        if (i == j) {
            //  i = i(real reach) + 1
            // because the condition of jumping out of "for", the i has been +1
            // it is not needed to +1 or -1
            helper(lists, 0, i);
        } else {
            // i = i(real reach)
            // becaues the condition of jumping out of "for", the i has been +1
            // we need to -1
            helper(lists, 0, i-1);
        }
        return;
    }
    // ---------------------------------------------------------------------
    // Solution 1-1
    // Divide the whole set of list into two subset
    // then divide every subset until we get two individual lists
    // merge two lists, then return to above layer to continue merging
    // finally, we get O(n * averageLen(List))
    ListNode* divide_conquer(vector<ListNode*>& lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        int mid = start + (end - start)/2;
        ListNode* left = divide_conquer(lists, start, mid);
        ListNode* right = divide_conquer(lists, mid+1, end);
        return mergetwo(left, right);
    }
    // ----------------------------------------------------------------------
    // commonly use
    // merge two with standard dummy method
    ListNode* mergetwo(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        if (l1) {
            tail->next = l1;
        } else {
            tail->next = l2;
        }
        return dummy.next;
    }
};

Similar problems

x

Tags

x