二路归并排序思想用一下结束

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param lists ListNode类一维数组 
 * @param listsLen int lists数组长度
 * @return ListNode类
 */

#include <malloc.h>
struct ListNode* merge(struct ListNode* head1,struct ListNode* head2){
    struct ListNode* p = head1;
    struct ListNode* q = head2;
    //哑变量
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = NULL;
    struct ListNode* temp = dummy;

    //合并
    while(p!=NULL&&q!=NULL){
        if(p->val>q->val){
            temp ->next = q;
            q = q ->next;
        }else{
            temp ->next = p;
            p = p->next;
        }
        temp = temp->next;
    }

    while(p!=NULL){
        temp->next = p;
        p = p->next;
        temp = temp->next;
    }
    while(q!=NULL){
        temp->next = q;
        q = q->next;
        temp = temp->next;
    }
    temp = NULL;
    return dummy->next;
}

/*递归merge*/
struct ListNode* mergeSort(struct ListNode** lists, int left,int right){
    if(left>=right){
        return lists[left];
    }
    int mid = (left+right)/2;
    struct ListNode* ll = mergeSort(lists,left,mid);
    struct ListNode* lr = mergeSort(lists, mid +1,right);
    return merge(ll,lr);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    return mergeSort(lists,0,listsLen-1);
}