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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
 #include"string.h"
 #include <math.h>
 #define CompareNode(a,b)  (a->val<b->val)


 //在一个排序链表里面插入一个新节点
struct ListNode*  InserNewNodetList(struct ListNode* head,struct ListNode*new)
{
    struct ListNode* p=head;
    if(CompareNode(new,head)==1)
    {
        new->next=head;
        return new;
    }
    while(p->next){
        if(CompareNode(new,p->next)==1){
              new->next=p->next;
              p->next=new;
              return head;
        }
        p=p->next;
    }
    p->next=new;      //插入链表最后
    new->next=NULL;
    return head;
}

//两个链表合并成一个排序的链表 ，返回排序链表的指针
struct ListNode*  SortList(struct ListNode*a ,struct ListNode*b)
{
   struct ListNode* pa=a,*pb=b,*pbuf; 
   if(pb==NULL||pa==NULL)
       return (pa==NULL ?  pb:pa);
   while(pb){
       pbuf=pb;
       pb=pb->next;                    
       pa=InserNewNodetList(pa,pbuf);  //从b链表里面取元素依次插入a链表
   }
   return pa;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode* pa=NULL;
    int i=1;
    pa=lists[0];
    while(i<listsLen){
        pa= SortList(pa,lists[i]);
        i++;
    }
    return pa;
}