有序链表合并

链表合并是指将两个有序链表合并成一个有序链表。可以通过递归的方式实现，具体步骤如下：

1. 如果两个链表中有一个为空，直接返回另一个链表。

2. 比较两个链表的头结点，将较小值的结点作为合并后链表的头结点。

3. 递归调用合并函数，将较小值结点的 next 指针指向递归调用返回的链表的头结点。

4. 返回合并后的链表。

以下是示例代码实现：

#include <iostream>
using namespace std;

// 链表结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(NULL) {}
};

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;
    }
}

int main() {
    // 构造链表1: 1->2->4
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);

    // 构造链表2: 1->3->4
    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);

    // 合并链表
    ListNode* l3 = mergeTwoLists(l1, l2);

    // 打印输出合并后的链表: 1->1->2->3->4->4
    while (l3 != NULL) {
        cout << l3->val << " ";
        l3 = l3->next;
    }

    return 0;
}