fork download
copy 
  1. // Merge K Sorted Lists [C++] (LC version 3.06).
  2.  
  3. #include <queue>
  4. #include <tuple>
  5. #include <iostream>
  6. using namespace std;
  7.  
  8. // List.
  9.  
  10. struct ListNode {
  11.     ListNode(int val=0, ListNode* next=nullptr)
  12.     : val(val), next(next)
  13.     {}
  14.     int val;
  15.     ListNode* next;
  16. };
  17.  
  18. ListNode* createList(const vector<int>& v)
  19. {
  20.     ListNode* s = nullptr;
  21.     for (auto i = v.rbegin(), n = v.rend(); i != n; ++i)
  22.         s = new ListNode(*i, s);
  23.     return s;
  24. }
  25.  
  26. void deleteList(ListNode* s)
  27. {
  28.     while (s) {
  29.         ListNode* next = s->next;
  30.         delete s;
  31.         s = next;
  32.     }
  33. }
  34.  
  35. void printList(ListNode* first)
  36. {
  37.     cout << '[';
  38.     for (ListNode* s = first; s; s = s->next)
  39.         cout << (s != first ? ", " : "") << s->val;
  40.     cout << "]\n";
  41. }
  42.  
  43. // Merge.
  44.  
  45. ListNode* mergeKLists(const vector<ListNode*>& lists)
  46. {
  47.     typedef tuple<int, int, ListNode*> T;
  48.     typedef priority_queue<T, vector<T>, greater<T>> pq_type;
  49.  
  50.     if (lists.empty())
  51.         return nullptr;
  52.  
  53.     pq_type q;
  54.     for (int k = 0, n = lists.size(); k < n; k++) {
  55.         ListNode* s = lists[k];
  56.         if (s)
  57.             q.emplace(s->val, k, s);
  58.     }
  59.  
  60.     if (q.empty())
  61.         return nullptr;
  62.  
  63.     for (ListNode temp, * t = &temp;;) {
  64.         auto [_, k, s] = q.top();
  65.         q.pop();
  66.         t->next = s;
  67.         if (q.empty())
  68.             return temp.next;
  69.         t = t->next;
  70.         s = s->next;
  71.         if (s)
  72.             q.emplace(s->val, k, s);
  73.     }
  74. }
  75.  
  76. // Show.
  77.  
  78. int main()
  79. {
  80.     ListNode* l0 = createList({});
  81.     ListNode* l1 = createList({1, 3, 5, 7});
  82.     ListNode* l2 = createList({2, 4, 6});
  83.     ListNode* l3 = createList({0, 4, 8});
  84.  
  85.     printList(l0);
  86.     printList(l1);
  87.     printList(l2);
  88.     printList(l3);
  89.  
  90.     printList(mergeKLists({}));
  91.     printList(mergeKLists({l0}));
  92.     printList(mergeKLists({l1}));
  93.     l0 = mergeKLists({l0, l1, l2, l3});
  94.     printList(l0);
  95.  
  96.     deleteList(l0);
  97. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[]
[1, 3, 5, 7]
[2, 4, 6]
[0, 4, 8]
[]
[]
[1, 3, 5, 7]
[0, 1, 2, 3, 4, 4, 5, 6, 7, 8]
https://ideone.com/DxvBNN
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!