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

1.两个有序链表合并的时间复杂度为N，合并K个链表要达到NlogN的时间复杂度，可以用归并的思想
2.归并排序的思想是，将一个大问题切割成小的问题，然后再将小的问题合并，
    比如将数组a一分为二成a1,a2，分别对这两部分排序，然后对这两个数组进行归并。
   对于a1，a2来说，又可以分别一分为二，a11,a12，a21,a22，一直这样切割，直到里面的元素只剩一个，那么就可以跟相邻的直接排序，这个过程为分解
   最后得到的一定是零散的有序数组，比如a11,a12已经排序OK，那么将这两个合并就得到a1的有序排列，这个过程为合并。
3. 合并K个有序链表，就类似归并排序的合并过程
    将K个链表首先分为前后两个部分，前k/2个和后k/2个，前后分别合并，一定会得到两个有序链表，再将这两个合并，就可以了
     前k/2个又可以按照前面的步骤继续分解，直到相邻的两个链表或者只剩下一个链表，就可以合并了
   

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param lists ListNode类一维数组
 * @param listsLen int lists数组长度
 * @return ListNode类
 */
#include <stdio.h>
#include <stdlib.h>
struct ListNode * mergetwolist(struct ListNode *p1, struct ListNode *p2)
{
    struct ListNode *new = NULL, *cur = NULL;

    new = (struct ListNode*)malloc(sizeof(struct ListNode));
    cur = new;

    while (p1 && p2) {
        if (p1->val <= p2->val)
        {
            cur->next = p1;
            p1 = p1->next;
        }
        else {
            cur->next = p2;
            p2 = p2->next;            
        }
        cur = cur->next;
    }

    if (p1)
    {
        cur->next = p1;
    }
    else {
        cur->next = p2;
    }

    cur = new->next;
    free(new);

    return cur;
}


void merge(struct ListNode **lists, int h, int t)
{
    int mid;
    struct ListNode *p1 = NULL, *p2 = NULL;
    struct ListNode *new = NULL;

    if (t >= h)
    {  
        /*当前是相邻的两个链表，则进行合并*/
        if ((t - h) == 1)
        {
//            printf("fffffffff\n");

            p1 = lists[h];
            p2 = lists[t];
            new = mergetwolist(p1, p2);
            lists[h] = new;
            return;
        }
        else if (t == h){
            return;
        }
    }

    mid = (t + h) / 2;
  //  printf("%d %d %d\n", t,h,mid);
    merge(lists, h, mid);
    merge(lists, mid + 1, t);
    new = mergetwolist(lists[h], lists[mid+1]);
    lists[h] = new;

    return;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    // write code here
    struct ListNode *fast = NULL, *slow = NULL;
    if(0 == listsLen)
    {
        return NULL;
    }

    merge(lists, 0, listsLen-1);

    return lists[0];
}