合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所有输入数据插入完为止。
示例:
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
思路
解法一：
- 使用虚拟头节点指向两个链表中 head 值最小的节点；
- 比较两个链表的节点值；
- 肯定有一方先结束，直接连接另一方剩余的节点。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dumpyNode = new ListNode(-1);
ListNode* prev = dumpyNode;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
prev->next = list1;
list1 = list1->next;
}else {
prev->next = list2;
list2 = list2->next;
}
prev = prev->next;
}
prev->next = list1 == nullptr ? list2 : list1;
return dumpyNode->next;
}
};