top145-#23

[LionCoder4ever]

• similar to merge sort

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       return merge(lists, 0, lists.size()-1);
    }

    ListNode* merge(vector<ListNode*>& lists, int l,int r) {
        if(l==r) return lists[l];
        if(l > r) return NULL;
        int mid = (l + r) >> 1;
        ListNode* i = merge(lists, l, mid);
        ListNode* j = merge(lists, mid+1, r);
        return mergeTwoList(i,j);
    }
    ListNode* mergeTwoList(ListNode* i, ListNode* j) {
        ListNode head;
        ListNode *cur = &head;
        while(i != NULL && j != NULL) {
            if(i->val < j->val) {
                cur->next = i;
               i = i->next;
            } else {
                cur->next = j;
                j = j->next;
            }
            cur = cur->next;
        }
        if(i!=NULL) {
            cur->next =  i;
        }
        if(j!=NULL) {
            cur->next = j;
        }
        return head.next;
    }
};