实现两个非递减有序单链表的合并操作且不引入额外的空间复杂度cpp

在C++中，合并两个非递减有序的单链表而不需要额外空间复杂度，可以采用迭代的方式逐节点比较并合并两个链表。下面是一个简单的示例代码：

#include <iostream>

// 定义链表节点结构
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) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 如果其中一个链表未遍历完，则添加剩余部分到结果链表
    if (l1)
        tail->next = l1;
    else
        tail->next = l2;

    return dummy->next;  // 返回合并后的实际头结点
}

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* mergedList = mergeTwoLists(list1, list2);

    // 打印合并后的链表
    while (mergedList) {
        std::cout << mergedList->val << " ";
        mergedList = mergedList->next;
    }

    return 0;
}

在这个例子中，`mergeTwoLists`函数会合并两个输入的有序链表，返回一个新的已排序的链表。注意，在这个过程中并没有创建新的链表节点，所以空间复杂度为O(1)，满足题目要求。