nikunjsoni

148

Mar 21st, 2021
68
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() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     struct compare{
  14.         bool operator()(const ListNode* a, const ListNode* b){
  15.             return a->val > b->val;
  16.         }
  17.     };
  18.    
  19.     ListNode* sortList(ListNode* head) {
  20.         priority_queue<ListNode*, vector<ListNode*>, compare> pq;
  21.         ListNode *dummy = new ListNode(0);
  22.         while(head){
  23.             pq.push(head);
  24.             head = head->next;
  25.         }
  26.         ListNode *curr = dummy;
  27.         while(!pq.empty()){
  28.             curr->next = pq.top();
  29.             pq.pop();
  30.             curr = curr->next;
  31.         }
  32.         curr->next = NULL;
  33.         return dummy->next;
  34.     }
  35. };
RAW Paste Data