C语言如何合并两个有序链表

C语言如何合并两个有序链表

有时候我们需要将两个有序的单链表合并成一个有序单链表，本文将介绍如何使用C语言实现此功能。

思路

将两个有序单链表合并成一个有序单链表，我们需要对两个表进行比较，以确定合并后的顺序。我们可以遍历两个链表，比较两个链表当前位置的节点大小，将较小的节点放入新链表中，直至遍历完两个链表其中之一，将没有遍历完的链表剩余节点加入新链表中即可。

代码示例：

    struct ListNode* mergeTwoLists(struct ListNode* l1, struct 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;
        }
    }
    

上述代码是使用递归实现两个有序单链表合并的函数，函数返回一个新的链表头节点。

代码说明：

• 代码第1-2行判断边界情况，如果其中一个链表为空，则直接返回另一个链表头节点。
• 代码第3-10行使用递归的方式将两个链表合并成一个链表。
• 代码第4-5行判断两个链表当前位置的节点大小，将较小的节点加入新链表中。然后递归调用mergeTwoLists函数，继续比较两个链表中后续的节点。
• 代码第6-8行与第4-5行类似，只不过此时将较小的节点为l2的头节点。

总结

本文介绍了如何使用C语言将两个有序单链表合并成一个有序单链表。我们使用递归的方式实现了该功能。在实际开发中，如果数据量过大，此方法可能会导致栈溢出的问题。因此在写代码时需要注意栈的大小问题。