用c++合并两个顺序表

在 C++ 中合并两个已排序的顺序表（也称为链表），通常有两种方法：

1. **迭代法**：
- 创建一个新的空链表作为结果。
- 使用两个指针分别指向第一个链表和第二个链表的头部。
- 比较两个链表当前节点的值，将较小的节点添加到新链表的尾部，并移动那个链表的指针。
- 重复这个过程，直到其中一个链表遍历完，然后将另一个链表剩余部分追加到结果链表。

struct ListNode {
    int val;
    ListNode* next;
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(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; // 返回新链表的实际头节点
}

2. **递归法**：
- 类似于上面的迭代法，但是使用递归来处理每个节点，最后返回新的头节点。

无论哪种方法，完成后你都会得到一个按升序排列的新链表。