合并升序单链表常规用双指针遍历取较小节点接入新链表，时间O(m+n)、空间O(1)，需用dummy节点统一入口并正确处理剩余链表；递归写法简洁但有栈溢出风险，须首行判空；降序只需改比较符；std::list须用merge()且要求已排序。
合并两个升序单链表的常规写法
直接用双指针遍历两个链表，每次取较小节点接入新链表尾部，时间复杂度 O(m + n)，空间复杂度 O(1)（不计返回链表）。关键在于处理好头节点和边界条件。
常见错误：忘记初始化 dummy 节点、漏判某链表提前走完、误用 == 比较指针值而非节点值。
- 必须用
ListNode* dummy = new ListNode(0)统一入口，避免空链表特判 - 循环条件是
l1 != nullptr && l2 != nullptr，不是l1->next或val判空 - 循环结束后，需手动接上非空剩余链表：
cur->next = l1 ? l1 : l2
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* cur = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return dummy.next;
}递归实现要注意栈深度和空指针访问
递归写法简洁但隐含风险：当链表长度超千级时可能触发栈溢出；且必须在首行检查 nullptr，否则 l1->val 会崩溃。
适用场景：教学演示、链表极短、或明确限制了最大长度（如 LeetCode 默认安全）。
立即学习“C++免费学习笔记（深入）”；
- 递归终止条件只能是
l1 == nullptr或l2 == nullptr，不能只写一个 - 递归调用前必须确保
l1和l2都非空，否则l1->next可能非法 - 返回的是“当前最小节点”，不是新分配节点，所以无需
new
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;
}
}合并降序链表只需改比较符号
算法结构完全一致，唯一区别是把 改成 >=。但要注意：如果输入链表方向不一致（一个升序一个降序），不能直接套用，必须先统一方向或改逻辑。
容易被忽略的点：有些题目要求“稳定合并”，即相同值时优先保留第一个链表的节点——此时需用 而非 ，否则会破坏稳定性。
- 升序合并用
l1->val val - 降序合并用
l1->val >= l2->val - 若要求稳定，一律用
或>=，禁用/>
使用 std::list 时不能直接复用指针逻辑
std::list 是双向链表容器，不暴露内部节点指针，也不允许你手动拼接 next 字段。想合并两个 std::list，得用成员函数 merge()，且要求两者都已排序。
错误做法：试图取 ::begin()
O(n²)。
- 调用前必须确保两个
std::list都已按同一规则排序（如都升序） -
list1.merge(list2)后，list2变为空，所有节点移入list1 - 若原始数据无序，先用
sort()，再merge()
std::lista = {1, 3, 5}; std::list b = {2, 4, 6}; a.merge(b); // a 变为 {1,2,3,4,5,6}，b 为空
实际写的时候，最常卡住的地方不是逻辑，而是空指针解引用和头节点管理——哪怕看懂了算法，少写一行 cur = cur->next 或错判一次 l1 是否为空，结果就全乱。
