C语言算法-解答合并 K 个升序链表问题的C语言实现

题目

给定 K 个升序链表，将它们合并为一个新的升序链表，并返回合并后的链表。

引言

合并 K 个升序链表问题需要考虑多个链表的合并和比较大小的逻辑。我们可以使用分治的方法来解决这个问题，将 K 个链表分成两半，分别合并，然后再将合并后的两个链表合并。解决这个问题需要对链表进行递归和指针操作。

算法思路

我们将使用分治的方法来解决合并 K 个升序链表问题。

算法的步骤如下：

1. 创建一个递归函数 mergeTwoLists，用于合并两个升序链表。该函数接受两个链表 l1 和 l2 作为参数，并返回合并后的链表。

2. 在递归函数中，首先判断递归终止条件：

   • 如果 l1 为空，返回 l2。
   • 如果 l2 为空，返回 l1。

3. 比较 l1 和 l2 的头结点的值：

   • 如果 l1 的头结点的值小于等于 l2 的头结点的值，将 l1 的头结点与合并后的链表的头结点相连，递归地合并 l1->next 和 l2。
   • 如果 l1 的头结点的值大于 l2 的头结点的值，将 l2 的头结点与合并后的链表的头结点相连，递归地合并 l1 和 l2->next。
4. 返回合并后的链表的头结点。
5. 在主函数中，使用分治的方法将 K 个升序链表依次两两合并，直到合并为一个链表。
6. 返回合并后的链表。

代码实现

下面是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) {
        return l2;
    }

    if (l2 == NULL) {
        return l1;
    }

    if (l1->val <= l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

ListNode* mergeKLists(ListNode** lists, int listsSize) {
    if (listsSize == 0) {
        return NULL;
    }

    int interval = 1;
    while (interval < listsSize) {
        for (int i = 0; i < listsSize - interval; i += interval * 2) {
            lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
        }
        interval *= 2;
    }

    return lists[0];
}

void printList(ListNode* head) {
    ListNode* current = head;

    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }

    printf("\n");
}

int main() {
    // 创建示例链表1: 1 -> 4 -> 5
    ListNode* l1 = (ListNode*)malloc(sizeof(ListNode));
    l1->val = 1;

    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    node1->val = 4;
    l1->next = node1;

    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    node2->val = 5;
    node1->next = node2;
    node2->next = NULL;

    // 创建示例链表2: 1 -> 3 -> 4
    ListNode* l2 = (ListNode*)malloc(sizeof(ListNode));
    l2->val = 1;

    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    node3->val = 3;
    l2->next = node3;

    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    node4->val = 4;
    node3->next = node4;
    node4->next = NULL;

    // 创建示例链表3: 2 -> 6
    ListNode* l3 = (ListNode*)malloc(sizeof(ListNode));
    l3->val = 2;

    ListNode* node5 = (ListNode*)malloc(sizeof(ListNode));
    node5->val = 6;
    l3->next = node5;
    node5->next = NULL;

    ListNode* lists[3];
    lists[0] = l1;
    lists[1] = l2;
    lists[2] = l3;

    printf("List 1: ");
    printList(l1);

    printf("List 2: ");
    printList(l2);

    printf("List 3: ");
    printList(l3);

    ListNode* result = mergeKLists(lists, 3);

    printf("Merged List: ");
    printList(result);

    // 释放内存
    while (result != NULL) {
        ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

算法分析

该算法使用了分治的思想，先将 K 个升序链表依次两两合并，然后再将合并后的链表继续两两合并，直到合并为一个链表。时间复杂度为 O(NlogK)，其中 N 是所有链表中的节点总数，K 是链表的数量。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入1:

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

示例输出1:

Merged List: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

示例输入2:

List 1: 
List 2: 
List 3: 

示例输出2:

Merged List: 空链表

示例输入3:

List 1: 
List 2: 1 -> 2 -> 3
List 3: 

示例输出3:

Merged List: 1 -> 2 -> 3

总结

本文使用C语言实现了解答合并 K 个升序链表问题的代码。通过使用分治的方法，我们能够将 K 个升序链表合并为一个新的升序链表。该算法的时间复杂度为 O(NlogK)，空间复杂度为 O(1)。