leetcode 23. 合并K个升序链表

题目描述：

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6]

解释：链表数组如下：

[

1->4->5,

1->3->4,

2->6

]

将它们合并到一个有序链表中得到。

1->1->2->3->4->4->5->6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/merge-k-sorted-lists

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

难度：困难

题解思路一：顺序合并

先合并两个链表，再处理剩下的链表。

C语言解答如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *mergeTwoList(struct ListNode *list1, struct ListNode *list2) {
    struct ListNode head;
    struct ListNode *tail = &head;
    struct ListNode *p1 = list1;
    struct ListNode *p2 = list2;

    if (p1 == NULL || p2 == NULL) {
        tail->next = p1 ? p1 : p2;
    }

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

    if (p1 == NULL || p2 == NULL) {
        tail->next = p1 ? p1 : p2;
    }

    return head.next;

}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    int i;
    struct ListNode *list = NULL;

    for (i = 0; i < listsSize; i++) {
        list = mergeTwoList(list, lists[i]);
    }

    return list;
}

题解思路二：分治合并

考虑优化方法一，用分治的方法进行合并。

C语言解答如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode *mergeTwoList(struct ListNode *list1, struct ListNode *list2)
{
    struct ListNode head;
    struct ListNode *tail = &head;
    struct ListNode *p1 = list1;
    struct ListNode *p2 = list2;

    if (p1 == NULL || p2 == NULL) {
        tail->next = p1 ? p1 : p2;
    }

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

    if (p1 == NULL || p2 == NULL) {
        tail->next = p1 ? p1 : p2;
    }

    return head.next;
}

struct ListNode *merge(struct ListNode** lists, int l, int r)
{
    int mid;
    struct ListNode *list1 = NULL;
    struct ListNode *list2 = NULL;

    if (l == r) {
        return lists[l];
    }

    if (l > r) {
        return NULL;
    }

    mid = (l + r) >> 1;

    list1 = merge(lists, l, mid);
    list2 = merge(lists, mid + 1, r);

    return mergeTwoList(list1, list2);
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    struct ListNode *list = NULL;

    list = merge(lists, 0, listsSize - 1);

    return list;
}

执行效果：

解法二优于解法一，执行用时间更短。