题目描述

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

样例

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

输出：1->2->3->4->5->5

算法

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

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

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

时间复杂度

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

C++ 代码

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

        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
            else 
            {
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }

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

        return dummy->next;
    }  
};