虚拟头结点的方式最为简便。

也是一种链表的解题方式。

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

虚拟结点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head=new ListNode(-1);
        ListNode* temp=head;
        while(list1&&list2){
            if(list1->valval){
                temp->next=list1;
                list1=list1->next;
            }
            else{
                temp->next=list2;
                list2=list2->next;
            }
            temp=temp->next;
        }
        temp->next=!list1?list2:list1;
        return head->next;
    }
};

这里的问题在于：合并之后，要链上剩余的部分，你得判断出来哪个更长一些。

由于ListNode这种并不是stl，无法取到长度。

那么我们就要不停的移动表头，然后找到非空的那一个就是了。

!list1?list2:list1表示的就是，如果list1是空的，那就说明剩余的是list2，我们接上list2就好了。

另外，在写的时候发现一个问题，那就是第一句ListNode* head=new ListNode(-1);

 这说明一个问题，我虽然是虚拟的，但是我最后要返回的是我的next，那么我不可能初始的时候就设置为空，那样的话没意义了，最后也取不到。

故，要是用new的方式的话，他就是一直存在的，而这之后的temp，才是指向了这一点，最后通过变化的temp进行的连接，使得最后可以返回head->next成为最后的结果。

---

递归

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

递归的思想很重要，但是复杂度会有点高。