21. 合并两个有序链表

难度：🟢 Easy | 标签：链表、递归 | 状态：⬜ LeetCode 链接

思路

dummy 哨兵节点 + 双指针拼接。每次取两链表当前更小的接到 tail 后面。

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode dummy(0), *tail = &dummy;
        while (a && b) {
            if (a->val <= b->val) { tail->next = a; a = a->next; }
            else                  { tail->next = b; b = b->next; }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }
};

复杂度

• 时间 O(m + n)，空间 O(1)
• 递归版：栈 O(m + n)

易错 / 回顾

• dummy 用栈对象省 delete
• 循环结束后剩下的接尾即可（不需要逐个接）
• 递归版很优雅，但 O(n) 栈空间