C++ solution, easy to understand, 32ms


  • 0
    1
    class Solution {
    public:
        ListNode* merge_two_list(ListNode* l1,ListNode* l2){
          ListNode* root=new ListNode(0);
          ListNode* tail=root;
          while(l1&&l2)
          {
            if(l1->val>l2->val)
            {
              tail->next=l2;
              l2=l2->next;
            }
            else
            {
              tail->next=l1;
              l1=l1->next;
            }
            tail=tail->next;
          }
          if(l1)tail->next=l1;
          else tail->next=l2;
          return root->next;
    
        }
        ListNode* merge_from_i_to_j(vector<ListNode*>& lists,int i,int j){
          if(i==j)return lists[i];
          int mid=(i+j)/2;
          return merge_two_list(merge_from_i_to_j(lists,i,mid),merge_from_i_to_j(lists,mid+1,j));
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
          int k=lists.size();
          if(k==0)return NULL;
          if(k==1)return lists[0];
          return merge_from_i_to_j(lists,0,k-1);
        }
    };

Log in to reply
 

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