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

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

 //将两链表合成一个新链表
struct ListNode *merge(struct ListNode* head1,struct ListNode *head2)
 {
    struct ListNode* H = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* h1 = head1;
    struct ListNode* h2 = head2;
    struct ListNode* h3 = H;
    while(h1 && h2)
    {
        if(h1->val < h2->val)
        {
            h3->next = h1;
            h1 = h1->next;
        }
        else
        {
            h3->next = h2;
            h2 = h2->next;
        }
        h3 = h3->next;
    }
    if(h1 == NULL)
    h3->next = h2;
    else
    h3->next = h1;
    return H->next;
 }

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) {
    if(listsLen == 0)
    return NULL;
    int i;
        for(i = 1;i<listsLen;i++)
        {
            lists[i] = merge(lists[i], lists[i-1]);
        }
        return lists[listsLen-1];
}