给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号 升序 记录于链表并返回。

注意：新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

**输入：**l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

**输入：**l1 = [], l2 = []
输出：[]

示例 3：

**输入：**l1 = [], l2 = [0]
输出：[0]

提示：

0 <= 链表长度 <= 1000

合并操作，我们需要一个指针来记录上一个插入到正确位置的元素是哪个，一个指针用来遍历

主要是头指针情况，此时上一个元素为空，无法直接操作。

我们可以考虑构造一个虚拟的公共结点作为头结点的前一个元素，这样可以在循环开始就使用pre了

记得最后返回公共结点的next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode *trainningPlan(ListNode *l1, ListNode *l2) {
        ListNode *pre = new ListNode(0);
        ListNode *ans = pre;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                pre->next = l1;
                pre = l1;
                l1 = l1->next;
            } else {
                pre->next = l2;
                pre = l2;
                l2 = l2->next;
            }
        }
        if (l2 != nullptr)
            pre->next = l2;
        if (l1 != nullptr)
            pre->next = l1;
        return ans->next;
    }
};