C语言怎么合并两个有序链表

1. 两个有序链表的合并

有序链表合并问题可以分成两个问题来考虑：第一个问题是如何将链表中的元素按照大小顺序合并，第二个问题是如何将两个有序链表合并成一个有序链表。

对于第一个问题，我们可以利用递归的思想，从链表的头节点开始，逐个比较链表中的元素大小，将较小的元素放到前面，直到链表排完为止。具体实现代码如下所示：

// 定义节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};
// 递归实现链表排序
struct ListNode* mergeSort(struct ListNode* l1, struct ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeSort(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeSort(l1, l2->next);
        return l2;
    }
}

对于第二个问题，即如何合并两个有序链表，我们可以分别从两个链表的头节点开始进行比较，将较小的元素加入新链表中，并将指针向后移动。具体实现代码如下所示：

// 迭代实现链表合并
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode dummy;
    dummy.next = NULL;
    struct ListNode* tail = &dummy;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    if (l1 != NULL) {
        tail->next = l1;
    }
    if (l2 != NULL) {
        tail->next = l2;
    }
    return dummy.next;
}

2. 问题分析与解决方案

2.1 问题分析

假设有两个有序链表A和B，它们的长度分别为n和m，现在我们要将它们合并成一个新的有序链表C。具体来说，就是将A和B中的元素按从小到大的顺序逐个加入C中。例如：

A链表：1 -> 3 -> 5 -> 7

B链表：2 -> 4 -> 6 -> 8

C链表：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

为了方便，我们假设节点中存储的是整数类型的元素。在C语言中，我们可以通过定义链表节点结构体来表示链表中的一个节点，如下所示：

// 定义节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

其中，val表示节点中存储的元素，next表示指向下一个节点的指针。由于是单向链表，因此只需要指向下一个节点的指针即可。

在实现链表合并算法之前，我们需要对问题进行进一步分析。在合并链表时，我们需要对比A和B中的元素大小，将较小的元素加入C中。因此，我们需要定义一个比较函数来比较节点的值大小，具体实现代码如下：

int cmp(struct ListNode* a, struct ListNode* b) {
    return a->val - b->val;
}

然后，我们就可以使用链表排序和链表合并算法来解决问题了。

2.2 解决方案

我们可以先对A和B中的元素进行排序，然后再进行合并。具体的流程如下：

先定义一个指向链表节点的指针p，初始值为头节点。

将A和B中的所有节点依次加入一个数组中（可以使用动态数组来实现），然后对数组进行排序，排序完成后依次将节点加入新的链表中。

在将节点加入新的链表C时，需要注意链表的头节点和尾节点的处理。

具体实现代码如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Compare function used when sorting the array of nodes.
 */
int cmp(const void* a, const void* b) {
    struct ListNode* node1 = *(struct ListNode**)a;
    struct ListNode* node2 = *(struct ListNode**)b;
    return node1->val - node2->val;
}
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    // If either list is empty, return the other list.
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    // Build an array of nodes from the input lists.
    int len1 = 0, len2 = 0;
    struct ListNode* p1 = l1;
    while (p1 != NULL) {
        len1++;
        p1 = p1->next;
    }
    struct ListNode* p2 = l2;
    while (p2 != NULL) {
        len2++;
        p2 = p2->next;
    }
    struct ListNode** arr = (struct ListNode**)malloc(sizeof(struct ListNode*) * (len1 + len2));
    int i = 0;
    p1 = l1;
    while (p1 != NULL) {
        arr[i++] = p1;
        p1 = p1->next;
    }
    p2 = l2;
    while (p2 != NULL) {
        arr[i++] = p2;
        p2 = p2->next;
    }
    // Sort the array of nodes.
    qsort(arr, len1 + len2, sizeof(struct ListNode*), cmp);
    // Build the output list from the sorted array.
    struct ListNode* head = arr[0];
    struct ListNode* tail = arr[0];
    for (int i = 1; i < len1 + len2; i++) {
        tail->next = arr[i];
        tail = tail->next;
    }
    tail->next = NULL;
    // Free the array of nodes.
    free(arr);
    // Return the head of the output list.
    return head;
}

3. 总结

本篇文章介绍了如何合并两个有序链表的算法。具体来说，我们可以使用链表排序和链表合并算法来解决问题。在实现过程中，需要定义一个比较函数来比较节点的值大小，然后对A和B中的元素进行排序，最后依次将节点加入新的链表中。