Leetcode: Merge k Sorted Lists

By | 2018 年 7 月 22 日

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

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Analysis

For this question, first throughs are:

  1. build a K-sized min-heap to pick first node from the smallest linked list;

  2. Binary merge 2 lists at a time. e.g. for a k=4 lists:
    First run, merge the lists indexed 0 and 1 and store in index 0;
    Then merge the lists indexed 2 and 3 and store in index 2;
    Finally, merge the lists indexed 0 and 2 and store in index 0;
    Return the list at index 0;

AS:

Both of them can be done in a O(log(k) * m) time, for m represent the average length of each list. So as the #2 method is more straight forward and doesn’t need to build the heap, I implemented in this way.

Notes

  • The linked list in the source may be empty, got this from test cases;
  • Use a temporary ListNode instance can simplify the process when merging 2 lists, comparing to just use a pointer (line22 in c++ code);
  • Always check break condition when writing while loop;
  • Draw a table to help figure out the equation of how to calculate group_base_index and group_step from step;

Solutions

C++, 16ms beats 99.5%

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    // Merge into list1.
    // From the test cases, the linked list in the source may be empty.
    ListNode* mergeTwoLists(ListNode* pList1, ListNode* pList2) {
        if(pList1 == NULL && pList2 == NULL) {
            return NULL;
        } else if(pList1 == NULL) {
            ListNode* temp = pList1;
            pList1 = pList2;
            pList2 = temp;
        }
        // so list1 must NOT be empty
        ListNode head(0); //store the merged list head
        ListNode* pLastNode = &head;
        while(pList1 && pList2) {
            // cout<<pList1->val<<" vs "<<pList2->val<<endl;
            ListNode** ppSmall = pList1->val <= pList2->val ? &pList1 : &pList2;
            ListNode* pSmallNode = *ppSmall;
            pLastNode->next = pSmallNode;
            pLastNode = pSmallNode;
            *ppSmall = (*ppSmall)->next;
        }
        pLastNode->next = pList1 ? pList1 : pList2;
        return head.next;
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int size = lists.size();
        if(size == 0) {
            return NULL;
        }
        int step = 1;
        while(step < size) {
            // group_base represents the base index of a group(pair).
            // step represents offset from group_base_index to the counterpart.
            // group_step represents offset between groups.
            int group_step = step * 2;
            for(int group_base = 0; group_base + step < size; group_base += group_step) {
                // cout<<group_base<<" "<<step<<endl;
                // sort group_base and group_base + step, merge into group_base
                lists[group_base] = mergeTwoLists(lists[group_base], lists[group_base + step]);
            }
            step *= 2;
        }
        return lists[0];
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注