题目

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

分析

合并k个排序的链表，返回已排序的结果。
对K个链表依次遍历，找到最小值，然后放入结果链表中，最后K个链表没有元素的时候退出。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    struct ListNode *ans=NULL,*last;
    while(1)
    {
        int min=1000000,mink=-1;
        for(int i=0;i<listsSize;i++)
        {
            if(lists[i]!=NULL&&lists[i]->val<min)
            {
                min=lists[i]->val;
                mink=i;
            }
        }
        //printf("%d %d\n",min,mink);
        if(mink==-1)break;
        lists[mink]=lists[mink]->next;
        struct ListNode *temp=(struct ListNode *)malloc(sizeof(struct ListNode));
        temp->val=min;
        temp->next=NULL;
        if(ans==NULL)
        {
            ans=temp;
            last=ans;
        }
        else
        {
            last->next=temp;
            last=temp;
        }
    }
    return ans;
}