将两个非递减的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其他的储存空间。表中允许有重复的数据，编写c++的代码

将两个非递减的有序链表合并成一个递增的有序链表可以采用迭代或者递归的方式来实现。这里我提供一种迭代的解决方案，它利用了两个指针分别遍历两个输入链表，并按照顺序添加节点到新的链表中。

#include <iostream>
using namespace std;

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 初始化头节点和临时指针
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;

    while (l1 && l2) {
        if (l1->val <= l2->val) {  // 如果l1较小，将其添加到新链表
            tail->next = l1;
            l1 = l1->next;
        } else {  // 否则，将l2添加
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;  // 更新尾部指针
    }

    // 添加剩余的链表节点（如果有一个链表未遍历完）
    if (l1) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return dummy->next;  // 返回合并后的链表头部
}

// 打印链表帮助测试
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

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);
    printList(result);  // 输出：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> nullptr

    return 0;
}