c语言实现两个有序链表的合并「代码示例」

1. 前言

链表是一种非常常见的数据结构，可以存储大量的数据，并且支持插入、删除、查找等操作。在实际开发中，经常需要对多个链表进行操作。比如，在一个有序链表中插入新节点，或者将两个有序链表合并成一个有序链表。本文主要介绍在C语言中如何实现两个有序链表的合并。

2. 有序链表的定义

有序链表是按照一定的顺序排列的链表，其每个节点都包含一个指向下一个节点的指针及一个数据项。在有序链表中，节点按照数据项升序排列。

2.1 有序链表的结构体定义

在C语言中，可以使用结构体来定义链表节点，其定义如下：

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

其中，val保存的是节点的数据，next指向下一个节点。

3. 合并两个有序链表

假设存在两个有序链表l1和l2，它们的元素按升序排列。现在需要将它们合并成一个有序链表l3，同样按升序排列。

3.1 迭代法

一种比较简单的方法是使用迭代法。定义三个指针p1、p2和p3，分别指向链表l1的头节点、链表l2的头节点和新链表l3的尾节点。然后比较p1和p2节点的大小，将较小的节点插入l3中，并将p1或p2向右移动，直到其中一个链表为空。最后，将另一个链表的剩余节点插入l3的尾部即可。

下面是迭代法的具体实现：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode dummy = {0};
    struct ListNode* tail = &dummy;
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    while (p1 && p2) {
        if (p1->val <= p2->val) {
            tail->next = p1;
            p1 = p1->next;
        } else {
            tail->next = p2;
            p2 = p2->next;
        }
        tail = tail->next;
    }
    tail->next = (p1 ? p1 : p2);
    return dummy.next;
}

上述代码中，我们定义了三个指针：指向新链表尾部的tail指针，指向链表l1的p1指针，指向链表l2的p2指针。在循环中，比较p1和p2节点的大小，将较小的节点插入l3中，并将p1或p2向右移动。

3.2 递归法

另一种方法是使用递归法。在递归中，将问题分解为两个子问题：将l1的头节点和合并后的l2合并；或者将l2的头节点和合并后的l1合并。将两个子问题的结果按升序排列即可得到最终结果。

下面是递归法的具体实现：

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

上述代码中，我们首先判断l1和l2是否为空。如果其中一个链表为空，直接返回另一个链表；否则，比较l1的头节点和l2的头节点的大小。将较小的节点的next指针指向合并后的链表，并递归地处理该节点的下一个节点。

4. 总结

本文介绍了在C语言中如何实现两个有序链表的合并。我们介绍了两种方法：迭代法和递归法。迭代法比较容易理解，适用于链表长度比较大的情况；递归法代码量比较少，但可能会因为递归深度过大而出现栈溢出等问题。

无论是哪种方法，在实际开发中都需要仔细考虑各种边界条件，避免出现空指针、悬垂指针等问题。同时，在合并链表时，我们需要注意保持新链表的有序性。