leetcode 23. Merge k Sorted Lists-蒲公英云

leetcode 23. Merge k Sorted Lists

男娘i 2022-07-29 09:19 233阅读 0赞

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路：大家看到hard，以为肯定很难，有什么刁钻解法，苦思冥想，迟迟不敲代码。小爷我看到后直接的思路就是把所有链表里的节点装入vector，sort，连接然后完事，简单粗暴。你要问这也行？不管三七二十一，试了再说。

struct mycomp
 { //自定义比较函数，重载“（）”操作符  
     bool operator() (const ListNode*a, const ListNode*b)
     {
         return a->val < b->val;
     }
 };
 class Solution {
 public:
     ListNode* mergeKLists(vector<ListNode*>& lists) {
         if (lists.empty())
             return NULL;
         vector<ListNode*>que;
         for (int i = 0; i < lists.size(); i++)
         {
             ListNode*node = lists[i];
             if (node != NULL)
             {
                 que.push_back(node);
                 while (node->next != NULL)
                 {
                     que.push_back(node->next);
                     node = node->next;
                 }
             }
         }
         if (!que.empty())
         {
             sort(que.begin(), que.end(), mycomp());
             for (int i = 0; i < que.size() - 1; i++)
                 que[i]->next = que[i + 1];
             que.back()->next = NULL;
             return que.front();
         }
         return NULL;
     }
 };