两个单链表递增有序合并一个有序的

当你有两个已排序的单链表，你需要将它们合并成一个新的有序链表。这个过程可以通过遍历两个链表，每次选择当前链表中的较小元素来构建新的链表。以下是一个简单的C++实现：

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2; // 如果l1为空，直接返回l2
    if (!l2) return l1; // 如果l2为空，直接返回l1

    // 创建一个新的头节点，初始指向l1
    ListNode* head = l1;
    if (l1->val > l2->val) { // 检查l1的第一个元素是否大于l2的第一个元素
        head = l2; // 将指针移动到l2
    }

    // 遍历两个链表，直到有一个链表遍历完
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            // 如果l1的值小于等于l2，将其添加到新链表
            l1 = l1->next;
        } else {
            // 否则，将l2的值添加到新链表
            l2 = l2->next;
        }
    }

    // 将剩余未遍历完的链表添加到新链表末尾
    head->next = l1 ? l1 : l2;

    return head;
}

// 测试示例
int main() {
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(2);
    list1->next->next = new ListNode(4);

    ListNode* list2 = new ListNode(1);
    list2->next = new ListNode(3);
    list2->next->next = new ListNode(4);

    ListNode* result = mergeTwoLists(list1, list2);
    // 打印结果
    while (result) {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << "\n";

    return 0;
}

在这个例子中，`mergeTwoLists` 函数接受两个已排序的链表 `l1` 和 `l2` 的头结点，然后按照升序顺序合并它们。如果某个链表已经遍历完，那么就直接将另一个链表剩余的部分添加到新链表。