fork download
copy 
  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. class node{
  7. public:
  8.     int data;
  9.     node* next;
  10.  
  11.     node(int d) {
  12.         data = d;
  13.         next = NULL;
  14.     }
  15. };
  16.  
  17. void insertAtTail(node* &head, int data){
  18.     //if there is no data 
  19.     if(head == NULL){
  20.         head = new node(data);
  21.         return;
  22.     }
  23.  
  24.     //otherwise need to find tail point
  25.     node*tail = head;
  26.     while(tail->next != NULL){
  27.         tail = tail->next;
  28.     }
  29.     tail->next = new node(data);
  30.     return;
  31. }
  32.  
  33. void printList(node *head) {
  34.     while(head != NULL) {
  35.         cout << head->data << " ";
  36.         head = head->next;
  37.     }
  38.     cout << endl;
  39. }
  40.  
  41. // Comparison object to be used to order the min-heap
  42. class compare{
  43. 	public:
  44.     bool operator() (node *lhs, node *rhs) {
  45.         return lhs->data > rhs->data;
  46.     }
  47. };
  48.  
  49.  
  50. // The main function to merge given `k` sorted linked lists.
  51. // It takes array `lists` of size `k` and generates the sorted output
  52. node *mergeKSortedList(vector<node *> &lists) {
  53.  
  54.     //create a empty min heap
  55.     priority_queue<node*, vector<node* >, compare> pq;
  56.  
  57.     // push the first node of each list into the min-heap
  58.     for (node* list: lists) {
  59.         pq.push(list);
  60.     }
  61.  
  62.     // take two pointers, head and tail, where the head points to the first node
  63.     // of the output list and tail points to its last node
  64.     node *head = NULL;
  65.     node *last = NULL;
  66.  
  67.     // run till min-heap is empty
  68.     while (!pq.empty())
  69.     {
  70.         // extract the minimum node from the min-heap
  71.         node* min = pq.top();
  72.         pq.pop();
  73.  
  74.         // add the minimum node to the output list
  75.         if (head == NULL) {
  76.             head = last = min;
  77.         }
  78.         else {
  79.             last->next = min;
  80.             last = min;
  81.         }
  82.  
  83.         // take the next node from the "same" list and insert it into the min-heap
  84.         if (min->next != NULL) {
  85.             pq.push(min->next);
  86.         }
  87.     }
  88.     // return head node of the merged list
  89.     return head;
  90. }
  91.  
  92. int main() {
  93.  
  94.     int k;
  95.     int n;
  96.  
  97.     cin >> k >> n;
  98.  
  99.     // an array to store the head nodes of the linked lists
  100.     vector<node *> lists; 
  101.  
  102.     //input
  103.  
  104.     for(int i=0;i<k;i++){
  105. 		node * head = NULL;
  106. 		for(int j=0;j<n;j++){
  107. 			int x;
  108. 			cin>>x;
  109. 			insertAtTail(head,x);
  110. 		}
  111. 		lists.push_back(head);
  112. 	}
  113.  
  114. 	node * ans = mergeKSortedList(lists);
  115. 	printList(ans);
  116.  
  117.  
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5380KB
comments (?)
stdin
copy 
3 4
1 2 3 4 5 6 7 8 9 10 11 12
stdout
copy 
1 2 3 4 5 6 7 8 9 10 11 12
https://ideone.com/aq3Aqk
language:
C++14 (gcc 8.3)
created:
3 years 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!