两个有序单链表合并C++

将两个已排序的单链表合并成一个新的有序单链表是一个常见的链表操作。你可以通过比较两个链表的头节点并选择较小的那个作为新链表的头，然后递归地对剩余部分进行同样的操作，直到其中一个链表为空。以下是C++的实现：

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;

    // 如果l1的值小于l2，那么l1的下一个节点将是新链表的第一个元素
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

这个函数会不断比较两个链表的当前节点，选择较小的节点并递归处理剩下的部分，直到两个链表都遍历完。最后返回的是新链表的头节点。

相关问题

分别输入两个有序的整数序列（分别包含M和N个数据），建立两个有序的单链表，将这两个有序单链表合并成为一个大的有序单链表，并依次输出合并后的单链表数据。c++

在 C++ 中，合并两个有序的整数链表可以采用迭代或递归的方式。这里我们先介绍一种常见的迭代方法：

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

ListNode* mergeTwoSortedLists(ListNode* l1, ListNode* l2) {
    // 创建一个新的头节点，初始为空
    ListNode* head = new ListNode(0);
    ListNode* tail = head;

    // 当任意一个链表还有元素时
    while (l1 != NULL && l2 != NULL) {
        // 比较当前两个链表的值，选择较小的那个添加到新链表中
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        // 更新tail指向下一个待插入的位置
        tail = tail->next;
    }

    // 如果其中一个链表已空，则将其剩余部分添加到新链表末尾
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return head->next;  // 返回合并后的链表头节点
}

// 示例：遍历并打印合并后的链表
void printList(ListNode* node) {
    while (node != nullptr) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

int main() {
    // 初始化两个有序链表
    // ...

    // 合并链表
    ListNode* mergedList = mergeTwoSortedLists(l1, l2);

    // 输出合并后的链表
    printList(mergedList);

    return 0;
}

编写算法：将两个有序单链表合并（一元多项式的表示和相加）c++实现代码并运行

在C++中，我们可以编写一个算法来合并两个已排序的单链表，然后表示它们作为一元多项式，并将这两个多项式相加。这里我们假设每个节点包含整数值，可以视为多项式系数。首先，我们需要定义一个链表结构以及用于合并和相加的操作。

#include <iostream>
using namespace std;

// 定义链表节点结构
struct ListNode {
    int val; // 节点值
    ListNode* next; // 指向下一个节点的指针
};

// 合并两个有序链表
ListNode* mergeSortedLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;

    if (l1->val < l2->val) {
        l1->next = mergeSortedLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeSortedLists(l1, l2->next);
        return l2;
    }
}

// 将链表转换为多项式表达式字符串
string listToPolynomial(ListNode* head) {
    string result = "";
    while (head != nullptr) {
        result += to_string(head->val) + "x^" + to_string(head->next == nullptr ? 0 : 1) + " ";
        head = head->next;
    }
    return result.substr(0, result.size() - 1); // 去掉末尾空格
}

int main() {
    // 创建示例链表
    ListNode* list1 = new ListNode{1, new ListNode{2, new ListNode{4, nullptr}}};
    ListNode* list2 = new ListNode{1, new ListNode{3, new ListNode{5, nullptr}}};

    // 合并链表
    ListNode* mergedList = mergeSortedLists(list1, list2);

    // 输出合并后的多项式
    cout << "合并后的多项式: " << listToPolynomial(mergedList) << endl;

    return 0;
}

在这个例子中，我们首先创建了两个已排序的链表`list1`和`list2`，然后通过`mergeSortedLists`函数合并它们。最后，我们使用`listToPolynomial`函数将合并后的链表转换成一元多项式形式并打印出来。

注意：这个程序假设链表存储的是从常数项到最高次项（一次项、常数项等），并且对于两个相同的值，先添加的链表会被优先选择。如果你想处理更复杂的场景（比如保留第一个出现的相同值），你需要对`mergeSortedLists`进行相应的修改。