面试题 25：合并两个排序的链表.md

试题链接：36. 合并两个排序的链表 - AcWing题库

方法一：迭代

• 思路：使用一个哨兵节点，然后不断在尾部添加链表中较小的一个节点即可，最后返回哨兵节点的下一个节点指针并释放哨兵节点内存。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        
        ListNode *head = dummy;
        
        while (l1 || l2) {
            if (l1 && l2) {
                if (l1->val < l2->val) {
                    head->next = l1;
                    l1 = l1->next;
                } else {
                    head->next = l2;
                    l2 = l2->next;
                }
            } else if (l1) {
                head->next = l1;
                break;
            } else if (l2) {
                head->next = l2;
                break;
            }
            head = head->next;
        }
        
        head = dummy->next;
        
        delete dummy;
        
        return head;
    }
};

方法二：递归

• 思路：选取两个链表中较小的节点作为最终的头节点，然后递归获得下一级的合并后的头结点。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (!l1 && !l2) return nullptr;
        if (l1 && !l2) return l1;
        if (!l1 && l2) return l2;
        
        ListNode *head;
        
        if (l1->val < l2->val) {
            head = l1;
            head->next = merge(l1->next, l2);
        } else {
            head = l2;
            head->next = merge(l1, l2->next);
        }
        
        return head;
    }
};