题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

$0 <= 链表长度 <= 1000$

注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/

---

算法

(二路归并) $O(n)$

新建一个虚拟头节点 dummy 用于存储合并两个链表后的新链表
根据归并的思想，两个指针 l1 和 l2 分别指向两个链表

0. 当 l1 和 l2 不为空时，循环比较两个指针指向节点的值的大小
1. 如果 l1->val < l2->val，把 l1 节点拿出来放到新链表的末尾，同时 l1 往后移
2. 如果 l1->val >= l2->val，把 l2 节点拿出来放到新链表的末尾，同时 l2 往后移
3. l1 和 l2 只要有一个为空循环结束，肯定有一个为空，另一个不为空，最后需要将不为空的部分接到新链表的末尾
4. 返回虚拟节点的 next 就是新链表的真正头节点

时间复杂度

两个链表各遍历一次，所以总时间复杂度为 $O(n)$

空间复杂度

$O(n)$，$n$ 为两个链表的长度之和

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1);
        auto cur = dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) cur->next = l1, l1 = l1->next, cur = cur->next;
            else cur->next = l2, l2 = l2->next, cur = cur->next; 
        }

        if (l1) cur->next = l1;
        if (l2) cur->next = l2;

        return dummy->next;
    }
};