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

题目描述:合并k个已排序的链表,并将其作为一个已排序的链表返回。分析并描述其复杂度。
示例1
        输入：[{1,2,3},{4,5,6,7}]
        返回值：{1,2,3,4,5,6,7}
思路：简单直接，利用一维数组将k个链表中的元素存储下来，然后对一维数组进行排序最后生成单链表返回即可。具体代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *res = (ListNode *)malloc(sizeof(ListNode)),*q=res;
        int k = lists.size();
        vector<int> r;
        for(int i=0;i<k;i++)
        {
            ListNode *p = lists[i];
            while(p!=NULL)
            {
                r.push_back(p->val);
                p = p->next;
            }
        }
        sort(r.begin(),r.end());
        for(int i=0;i<r.size();i++)
        {
            ListNode *t = (ListNode *)malloc(sizeof(ListNode));
            t->val = r[i];
            t->next = NULL;
            q->next = t;
            q = q->next;
        }
        return res->next;
    }
};