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

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

struct ListNode* mergeKLists(struct ListNode** lists, int listsLen ) 
{
    if(lists == NULL) return NULL;
    
    int i = 1;
    struct ListNode *newHead = *lists;
    while(i < listsLen)
    {
        struct ListNode *PTR = *(lists+i);
        newHead = mergeTwoLists(newHead, PTR);
        i++;
    }//将输入数组中的链表两两merge
    
    return newHead;
}

struct ListNode* mergeTwoLists(struct ListNode *list1, struct ListNode *list2)
{
    if(!list1) return list2;
    if(!list2) return list1;

    if(list1->val > list2->val)
    {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
    else 
    {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    }//使用递归方法merge两个升序链表
}