I am learning C++ out of my own interest. I have come across a situation that i can not logically understand.
I am trying to solve this problem : https://leetcode.com/problems/merge-k-sorted-lists/ , with the help of Min Heap. I am using priority queue as a min heap.
Now my code looks something like this :
ListNode* mergeKLists(vector<ListNode*>& lists) {
struct Compare {
bool operator() (const ListNode *a, const ListNode *b) {
return a->val > b->val;
}
};
// Use min heap to keep the smallest node of each list
priority_queue<ListNode *, vector<ListNode *>, Compare> min_heap;
for (auto n : lists) {
if(n){
min_heap.push(n);
}
}
.
.
.
.
}
I am getting the correct output.
The code min_heap.push(n); is pushing the entire linked list in the min_heap , i am not sure why is that happening.
It should only push the first element of the linked list into the min_heap . right ?
Please let me know.
The structure of Nodes look like this :
struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
With that kind of Node data structure, the reference to your first node is also the reference to your linked list, because the first node has next pointing to the second, then next->next will be pointing to the third... etc. So it is behaving as expected.
Current behaviour
After the execution of the for loop, you will have the queue with the first element of each linked list (which also contains the pointer to the rest of the linked list, but are not contained in the queue) sorted by value. Check its size and you'll see.
Expected behaviour
For what I've seen in the exercise, you need to insert not only the first node of each linked list, but all of them, so you should make a nested for loop to add, for each list, every node:
for (auto n : lists){ // for every list
ListNode* iterator = n;
// I assume that your last element in each list has next pointing to null
while(iterator) { // add all the nodes
min_heap.push(iterator);
iterator = iterator->next;
}
}
This will add every node in the list separately to the queue.
Important: If you use a function that prints linked lists, you will see a lot of repetitions here, because of the same reason that you saw the whole linked list in your first attempt. To see exactly what nodes are stored in the queue, you have to use a function that prints only the value of the node and doesn't uses next.