Merge k Sorted LIsted Exceed time limit


  • 0
    Z

    Not sure what improvement should I make. Thanks for any suggestion

    /**

    • 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.size() == 0)
      return NULL;

       if(lists.size() == 1)
           return lists[0];
      
       ListNode dummy(-1);
       dummy.next = NULL;
       ListNode *cur = &dummy;
      
       while(cur){
           int min_index = -1;
           int min_val =INT_MAX;
           for(int i = 0; i < lists.size(); i++){
               if(lists[i] != NULL && lists[i]->val < min_val){
                   min_val = lists[i]->val;
                   min_index = i;
               }
           }
           
           if(min_index == -1){
               cur->next = NULL;
               break;
           }
           cur->next = lists[min_index];
           if(lists[min_index] != NULL)
               lists[min_index] = lists[min_index]->next;
           cur = cur->next;
       }
       return dummy.next;
      

      }
      };


  • 0
    S

    The problem is that you are looking for the minimum value in each linked list every single iteration.
    Try to use merge sort idea.
    split the whole range into half and merge each independently.

    For Example you have 10 lists:

    merge lists from 0 to 10
        firstlist = merge lists from 0 4
        secondlist = merge lists from 5 9
    
        // do merge of 2 linked lists here.

  • 0
    D

    Yeal, ur right!


Log in to reply
 

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