Merge sort, recursion


  • 0
    G
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if (lists.empty()) {
                return NULL;
            }
            mergeSort(lists, 0, lists.size() - 1);
            return lists[0];
        }
    private:
        void mergeSort(vector<ListNode*>& lists, const int l, const int r) {
            if (l >= r) {
                return;
            }
            int mid = l + ((r - l) >> 1);
            mergeSort(lists, l, mid);
            mergeSort(lists, mid + 1, r);
            lists[l] = mergeTwo(lists[l], lists[mid + 1]);
        }
        ListNode* mergeTwo(ListNode* a, ListNode* b) {
            if (a == NULL) {
                return b;
            }
            if (b == NULL) {
                return a;
            }
            if (a -> val < b -> val) {
                a -> next = mergeTwo(a -> next, b);
                return a;
            } else {
                b -> next = mergeTwo(a, b -> next);
                return b;
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.