C++ O(Nlog(N)) solution by set


  • 0
    T

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      /
      #define mp make_pair
      class Solution {
      public:
      ListNode
      mergeKLists(vector<ListNode*>& lists) {
      if(lists.size() == 0) return NULL;
      ListNode* ans = NULL, haha = NULL;
      set < pair <int , pair < ListNode
      , int > > > s;
      set < pair <int , pair < ListNode*, int > > >::iterator it;

       for(int i=0; i<lists.size(); i++)
           if(lists[i] != NULL)
               s.insert(mp(lists[i]->val, mp(lists[i], i)));
      
       while(!s.empty())  {
          it = s.begin();    
          pair <int , pair < ListNode*, int > > cur = *it;
          if(ans == NULL) {
              ans = cur.second.first;
              haha = ans;
          }
          else {
              ans->next = cur.second.first;
              ans = ans->next;
          }
          s.erase(it);
          lists[cur.second.second] = lists[cur.second.second]->next; 
          
          if(lists[cur.second.second] != NULL)
          s.insert( mp (lists[cur.second.second]->val , mp(lists[cur.second.second], cur.second.second) )  );
      }
       return haha;
      

      }
      };


Log in to reply
 

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