21题

方法：迭代—-分情况比较多，官方方法会比较简单

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1&&!list2){
            return NULL;
        }
        ListNode* head1=list1;
        ListNode* head2=list2;
        ListNode* result=NULL;
        ListNode* result1;
        while(list1&&list2){
            int n1=list1->val;
            int n2=list2->val;
            if(n1<n2){
                if(result==NULL){
                    result=new ListNode(n1);
                    result1=result;
                    list1=list1->next;
                }else{
                    result->next=new ListNode(n1);
                    result=result->next;
                    list1=list1->next;
                }
            }else{
                if(result==NULL){
                    result=new ListNode(n2);
                    result1=result;
                    list2=list2->next;
                }else{
                    result->next=new ListNode(n2);
                    result=result->next;
                    list2=list2->next;
                }
            }
        }
        if(list1&&!list2){
            if(result==NULL){
                return list1;
            }
            result->next=list1;
        }
        if(!list1&&list2){
            if(result==NULL){
                return list2;
            }
            result->next=list2;
        }
        return result1;
    }
};