SHARE
TWEET

Untitled

a guest May 25th, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* mergeKLists(vector<ListNode*>& lists)
  12.     {
  13.         if (lists.size()==0) return nullptr;
  14.         size_t delta = 1;
  15.         while (delta < lists.size())
  16.         {
  17.             for (int i=0; i<lists.size()-delta; i=i+2*delta)
  18.                 lists[i] = mergeTwoLists(lists[i], lists[i+delta]);
  19.             delta *= 2;
  20.         }
  21.        
  22.         return lists[0];
  23.     }
  24.    
  25.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
  26.     {
  27.         if (l1 == NULL) return l2;
  28.         if (l2 == NULL) return l1;
  29.  
  30.         auto v1 = l1->val;
  31.         auto v2 = l2->val;
  32.         auto root = v1 <= v2 ? l1 : l2;
  33.         v1 <= v2 ? (l1 = l1->next) : (l2 = l2->next);
  34.  
  35.         auto cur = root;
  36.         while (l1 != NULL && l2 != NULL)
  37.         {
  38.             if (l1->val <= l2->val)
  39.             {
  40.                 cur->next = l1;
  41.                 l1 = l1->next;
  42.             }
  43.             else
  44.             {
  45.                 cur->next = l2;
  46.                 l2 = l2->next;
  47.             }
  48.             cur = cur->next;
  49.         }
  50.         cur->next = l1 != NULL ? l1 : l2;
  51.  
  52.         return root;
  53.     }
  54. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top