合并两个已排序单链表可通过递归或迭代实现，推荐迭代法。首先定义链表节点结构，递归法比较节点值选择较小者递归合并，迭代法使用虚拟头节点循环连接较小节点，时间复杂度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 val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
迭代法合并链表
使用循环方式，通过一个虚拟头节点（dummy）简化边界处理，逐个连接较小的节点。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* curr = &dummy;
while (l1 && l2) {
if (l1->val 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)（不计递归栈），适合实际应用。
基本上就这些。根据需求选择递归或迭代方式，推荐迭代法用于生产环境，更稳定且节省栈空间。
