c++中如何合并两个链表_c++链表合并实现方法

合并两个已排序单链表可通过递归或迭代实现，推荐迭代法。首先定义链表节点结构，递归法比较节点值选择较小者递归合并，迭代法使用虚拟头节点循环连接较小节点，时间复杂度O(m+n)，空间复杂度O(1)，适合生产环境。

在C++中合并两个链表通常指的是将两个已排序的单链表合并为一个新的有序链表。新链表由原链表的节点拼接而成，不需要创建额外的节点（除非特别要求）。下面介绍常见的实现方法。

定义链表结构

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

递归法合并链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val < l2->val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

迭代法合并链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }

    curr->next = l1 ? l1 : l2;

    return dummy.next;
}

立即学习“C++免费学习笔记（深入）”；

这种方法避免了频繁的内存分配，时间复杂度为 O(m + n)，空间复杂度 O(1)（不计递归栈），适合实际应用。

基本上就这些。根据需求选择递归或迭代方式，推荐迭代法用于生产环境，更稳定且节省栈空间。

以上就是c++++中如何合并两个链表_c++链表合并实现方法的详细内容，更多请关注php中文网其它相关文章！