Merge k Sorted Lists

解题思路

  1. 归并排序。

  2. 由此可见，基础多重要，我一开始想到的是挨个遍历，没有意识到这是归并排序场景的替换。

  3. 分别实现了递归的 Top-Down 和迭代的 Bottom-Up，一开始递归解法是迭代的解法的耗时两倍，加上 Key Line 耗时就一样了。没有这一行的话，函数调用是没有必要的，多出了很多函数调用的开销。

代码

// Top-Down
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return _merge(lists, 0, lists.size());
    }
    
    ListNode* _merge(vector<ListNode*>& lists, int left, int right) {
        if (left >= right) {
            return NULL;
        } else if (left == right-1) {
            return lists[left];
        } else if (left == right-2) {
            // Key Line
            return mergeTwoLists(lists[left], lists[left+1]);
        }
        int mid = left + (right - left) / 2;
        ListNode* NodeL = _merge(lists, left, mid);
        ListNode* NodeR = _merge(lists, mid, right);
        return mergeTwoLists(NodeL, NodeR);
    }
    
    ListNode* mergeTwoLists(ListNode* ListA, ListNode* ListB) {
        ListNode dummy(-1);
        ListNode* head = &dummy;
        while (ListA && ListB) {
            if (ListA->val < ListB->val) {
                head->next = ListA;
                ListA = ListA->next;
            } else {
                head->next = ListB;
                ListB = ListB->next;
            }
            head = head->next;
        }
        if (ListA) {
            head->next = ListA;
        } else {
            head->next = ListB;
        }
        return dummy.next;
    }
};

// Bottom-Up
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (n == 0) {
            return nullptr;
        }
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n/2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i+k]);
            }
            n = k;
        }
        return lists[0];
    }
    
    ListNode* mergeTwoLists(ListNode* ListA, ListNode* ListB) {
        ListNode dummy(-1);
        ListNode* head = &dummy;
        while (ListA && ListB) {
            if (ListA->val < ListB->val) {
                head->next = ListA;
                ListA = ListA->next;
            } else {
                head->next = ListB;
                ListB = ListB->next;
            }
            head = head->next;
        }
        if (ListA) {
            head->next = ListA;
        } else {
            head->next = ListB;
        }
        return dummy.next;
    }
};