Merge k Sorted Lists ——待解决TLE

我就是我 2022-08-08 06:25 201阅读 0赞

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

【分析】

思路基于两个有序链表合并。只不过每次都需要遍历选出K个链表中最小的那个数。

【代码】

下面的代码始终LTE，原因是一个很长的case超时，改了好久也没有改对，希望后面可以纠正！

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        int n=lists.size();
        if(n==0)return NULL;      
        ListNode *head=new ListNode(INT_MIN);
        ListNode *ret=head;
        int min; 
        bool finish;
        while(1)
       {
          finish=true;
          min=INT_MAX;
          int i;int mini;
          for(i=0;i<lists.size();i++)
          {
             if(lists[i]!=NULL)
             {
                if(lists[i]->val<min)
                {
                    min=lists[i]->val;
                    mini=i;
                    finish=false;
                }
             }           
          }
          if(finish)break;   
          head->next=lists[mini];
          head=head->next;
          lists[mini]=lists[mini]->next;     
       }
       return ret->next;
    }
};