题解 | #合并k个已排序的链表#

/**
分享一个投机取巧的方法
观察题目可以看到取值为-1000~1000一共才2001个值，而list数量高达10^5，因此在暴力找最小之后，扫一遍所有链表头，把值相同的全连进返回值里面去，可以刚好卡进及格线
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *ret=NULL;
        ListNode *retHead=NULL;
        //int finishListNum=lists.size();
        while(1)
        {
            int tmpMinIndex=-1;
            //find min node
            for(int i=0;i<lists.size();i++)
            {
                if(lists[i]==NULL)
                    continue;
                if(tmpMinIndex==-1)//初始化
                {
                    tmpMinIndex=i;
                    continue;
                }
                if(lists[i]->val<lists[tmpMinIndex]->val)
                {
                    tmpMinIndex=i;
                }
            }
            if(tmpMinIndex==-1)
                break;
            int tmpCurrVal=lists[tmpMinIndex]->val;
            //link
            if(ret==NULL)
                retHead=ret=lists[tmpMinIndex];
            else
            {
                ret->next=lists[tmpMinIndex];
                ret=ret->next;
            }
            lists[tmpMinIndex]=lists[tmpMinIndex]->next;
            //因节点取值很少，加速一下
            for(int i=0;i<lists.size();i++)
            {
                if(lists[i]==NULL)
                    continue;
                if(lists[i]->val==tmpCurrVal)
                {
                    ret->next=lists[i];
                    ret=ret->next;
                    lists[i]=lists[i]->next;
                }
            }
        }
        return retHead;
    }
};