合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:[  1->4->5,  1->3->4,  2->6]输出: 1->1->2->3->4->4->5->6

思路：k个链表是排好序的，那我们就可以依次，按顺序的比较每个链表的节点，将最小的依次放入一个新链表中。我的做法是动态申请一个指针数组，每个链表均由一个指针指向，然后就可以比较每个链表的值，直到每个链表为空。这里注意在遍历的时候要注意判断是否为空，否则就会出现一个链表为零，还在比较它的节点大小的情况，访问出错。

ListNode* mergeKLists(vector
     
      & lists)     {        ListNode* newhead=new ListNode(0);        ListNode* cur=newhead;        int len=lists.size();        if(len==0) return NULL;        ListNode** p=new ListNode*[len];        for(int i=0;i
      
       p[i]->val  )//找到最小的节点，并记录链表的下标                {                    pos=i;                    min=p[i]->val;                }            }        if(p[pos])//不为空挂在后面，否则意味着全为空了，退出        {        cur->next=new ListNode(p[pos]->val);        p[pos]=p[pos]->next;        cur=cur->next;        }        else        break;        }    return newhead->next;}
      
     

其实我们可以用优先队列来完成找最小节点的任务。

struct cmp {    bool operator() (const ListNode* a, const ListNode* b)    {        return a->val > b->val;    }};class Solution {public:    ListNode* mergeKLists(vector
     
      & lists) {        priority_queue
      
       , cmp> heap;        ListNode *head = new ListNode(0);        ListNode *curr = head;        auto iter = lists.begin();        for (; iter != lists.end(); iter++)         {            if (*iter != NULL)             {                heap.push(*iter);            }        }        while (!heap.empty())        {            ListNode* minNode = heap.top();            heap.pop();            ListNode* tmp = new ListNode(minNode->val);            curr->next = tmp;            curr = curr->next;            if (minNode->next != NULL)            {                heap.push(minNode->next);            }        }                return head->next;    }};